Gần hành tinh Hỏa, trong một thiên hà xa xôi kỳ lạ rất giống với thiên hà của chúng ta, đang diễn ra một cuộc chiến sinh tử giữa lực lượng đế chế và quân phiến loạn. Quân đội phiến loạn có \(N\) con tàu, chúng ta sẽ coi chúng là các điểm \((x_i, y_i, z_i)\). Mỗi con tàu có một bộ thu với công suất \(p_i\). Quân phiến loạn cần có khả năng gửi thông điệp từ tàu tuần dương trung tâm đến tất cả các con tàu, nhưng họ đang eo hẹp về tài chính nên không thể trang bị một bộ phát quá mạnh.

Nếu tàu tuần dương được đặt tại \((x, y, z)\), và một trong các con tàu khác ở \((x_i, y_i, z_i)\) có bộ thu công suất \(p_i\), thì công suất bộ phát của tàu tuần dương cần ít nhất là:

(|xi - x| + |yi - y| + |zi - z|) / pi

Nhiệm vụ của bạn là tìm vị trí đặt tàu tuần dương sao cho cực tiểu hóa công suất cần thiết cho bộ phát của nó, và in ra công suất đó.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test nối tiếp theo sau.

Mỗi bộ test chứa số nguyên \(N\) ở dòng đầu tiên, là số lượng con tàu trong bộ test đó.

\(N\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_i, y_i, z_i\) và \(p_i\), cách nhau bởi các khoảng trắng đơn. Đây là tọa độ của con tàu thứ \(i\) và công suất bộ thu của nó. Có thể có nhiều hơn một con tàu ở cùng một tọa độ.

Dữ liệu ra

Đối với mỗi bộ test, bạn nên xuất ra:

Case #X: Y

trong đó X là số thứ tự của bộ test và Y là công suất tối thiểu đủ để tiếp cận tất cả các con tàu trong hạm đội. Các câu trả lời có sai số tương đối hoặc tuyệt đối không quá \(10^{-6}\) sẽ được coi là chính xác.

Ràng buộc

• \(1 \le T \le 10\)
• \(0 \le x_i, y_i, z_i \le 10^6\)
• \(1 \le p_i \le 10^6\)

Phân nhóm

• Small dataset (Test set 1 - Visible): \(1 \le N \le 10\)
• Large dataset (Test set 2 - Hidden): \(1 \le N \le 1000\)

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
4
0 0 0 1
1 2 0 1
3 4 0 1
2 1 0 1
1
1 1 1 1
3
1 0 0 1
2 1 1 4
3 2 3 2

Case #1: 3.50000000
Case #2: 0.00000000
Case #3: 2.33333333

Nguồn

Google Code Jam 2008, Vòng 2, bài Star Wars.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.