Description

你正在研究一群 $N$ 只萤火虫。每只萤火虫都以恒定速度沿直线运动。你站在宇宙的中心，即位置 $(0, 0, 0)$。每只萤火虫的质量都相同，你想知道这群萤火虫的质心距离你的位置（原点）最近会有多近。

你已知每只萤火虫在 $t = 0$ 时的初始位置和速度，且只关心 $t \geq 0$ 的情形。萤火虫们速度恒定，可以自由穿越空间，包括互相穿过和穿过你。设 $M(t)$ 表示 $N$ 只萤火虫在时刻 $t$ 的质心位置，$d(t)$ 表示你的位置到 $M(t)$ 的距离。请你求出 $d(t)$ 的最小值 $d_{\text{min}}$，以及最早使 $d(t) = d_{\text{min}}$ 的时刻 $t_{\text{min}}$。

Input Format

输入的第一行包含一个整数 $T$，表示测试用例数。每个测试用例第一行为一个整数 $N$，表示萤火虫的数量，接下来有 $N$ 行，每行格式如下：

$x\ y\ z\ v_x\ v_y\ v_z$

每行描述一只萤火虫：$(x, y, z)$ 是其在 $t = 0$ 时的初始位置，$(v_x, v_y, v_z)$ 是其速度。

Output Format

对于每个测试用例，输出

Case #$X$: $d_{\text{min}}$ $t_{\text{min}}$

其中 $X$ 是测试编号（从 1 开始），$d_{\text{min}}$ 是最小距离，$t_{\text{min}}$ 是达到最小距离的最早时刻。你的答案只要绝对误差或相对误差不超过 $10^{-5}$ 即视为正确。

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

Hint

说明

给定 $N$ 个点 $(x_i, y_i, z_i)$，它们的质心为 $(x_c, y_c, z_c)$，其中：

• $x_c = (x_1 + x_2 + \ldots + x_N) / N$
• $y_c = (y_1 + y_2 + \ldots + y_N) / N$
• $z_c = (z_1 + z_2 + \ldots + z_N) / N$

限制条件

• 输入中的所有数均为整数。
• $1 \leq T \leq 100$
• $x$、$y$、$z$、$v_x$、$v_y$、$v_z$ 的取值范围均为 $-5000$ 到 $5000$，包含端点。

小数据集（10 分）

• $3 \leq N \leq 10$

大数据集（17 分）

• $3 \leq N \leq 500$

翻译由 ChatGPT-4.1 完成。