Bạn đang nghiên cứu một đàn gồm \(N\) con đom đóm. Mỗi con đom đóm đang di chuyển trên một đường thẳng với tốc độ không đổi. Bạn đang đứng ở tâm của vũ trụ, tại vị trí \((0, 0, 0)\). Mỗi con đom đóm có khối lượng như nhau và bạn muốn biết tâm của đàn đom đóm sẽ tiến gần đến vị trí của bạn (gốc tọa độ) như thế nào.

Bạn biết vị trí và vận tốc của mỗi con đom đóm tại thời điểm \(t = 0\), và chỉ quan tâm đến \(t \ge 0\). Các con đom đóm có vận tốc không đổi và có thể đi xuyên qua mọi không gian, bao gồm cả nhau và cả bạn. Gọi \(M(t)\) là vị trí tâm khối của \(N\) con đom đóm tại thời điểm \(t\). Gọi \(d(t)\) là khoảng cách giữa vị trí của bạn và \(M(t)\) tại thời điểm \(t\). Tìm giá trị nhỏ nhất của \(d(t)\), \(d_{min}\), và thời điểm sớm nhất khi \(d(t) = d_{min}\), \(t_{min}\).

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên đơn lẻ \(T\), số lượng bộ thử nghiệm. Mỗi bộ thử nghiệm bắt đầu bằng một dòng chứa một số nguyên \(N\), số lượng đom đóm, tiếp theo là \(N\) dòng có dạng:

x y z vx vy vz

Mỗi dòng này mô tả một con đom đóm: \((x, y, z)\) là vị trí ban đầu của nó tại thời điểm \(t = 0\), và \((vx, vy, vz)\) là vận tốc của nó.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất:

Case #X: dmin tmin

trong đó \(X\) là số thứ tự bộ thử nghiệm, bắt đầu từ 1. Bất kỳ câu trả lời nào có sai số tuyệt đối hoặc tương đối không quá \(10^{-5}\) đều sẽ được chấp nhận.

Ràng buộc

• Tất cả các số trong dữ liệu vào đều là số nguyên.
• \(1 \le T \le 100\)
• Các giá trị của \(x, y, z, vx, vy\) và \(vz\) sẽ nằm trong khoảng từ \(-5000\) đến \(5000\), bao gồm cả hai đầu mút.

Phân nhóm

• Tập dữ liệu nhỏ (Small dataset): \(3 \le N \le 10\).
• Tập dữ liệu lớn (Large dataset): \(3 \le N \le 500\).

Đ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
3
3 0 -4 0 0 3
-3 -2 -1 3 0 0
-3 -1 2 0 3 0
3
-5 0 0 1 0 0
-7 0 0 1 0 0
-6 3 0 1 0 0
4
1 2 3 1 2 3
3 2 1 3 2 1
1 0 0 0 0 -1
0 10 0 0 -10 -1

Case #1: 0.00000000 1.00000000
Case #2: 1.00000000 6.00000000
Case #3: 3.36340601 1.00000000

Ghi chú

Cho \(N\) điểm \((x_i, y_i, z_i)\), tâm khối của chúng là điểm \((x_c, y_c, z_c)\), trong đó:

xc = (x1 + x2 + ... + xN) / N
yc = (y1 + y2 + ... + yN) / N
zc = (z1 + z2 + ... + zN) / N

Nguồn

Google Code Jam 2009, Vòng 1C, bài Center of Mass.

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