Description

在遥远的银河系中，火星附近正爆发着帝国军与反叛军之间的殊死战斗。反叛军拥有 $N$ 艘飞船，我们将每艘飞船视为一个点 $(x_i, y_i, z_i)$。每艘飞船都配备了接收器，其接收功率为 $p_i$。反叛军需要能够从中央巡洋舰向所有飞船发送消息，但由于经费紧张，他们无法负担高功率的发射器。

如果巡洋舰被放置在 $(x, y, z)$，而另一艘飞船位于 $(x_i, y_i, z_i)$，其接收功率为 $p_i$，那么巡洋舰的发射器功率至少需要为：

你的任务是找到一个巡洋舰的位置，使得所需的发射器功率最小，并输出该最小功率。

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。

每组测试数据的第一行为整数 $N$，表示该组中飞船的数量。

接下来的 $N$ 行，每行包含四个整数 $x_i, y_i, z_i, p_i$，用空格分隔，分别表示第 $i$ 艘飞船的坐标和接收功率。可能有多艘飞船位于相同坐标。

Output Format

对于每组输入数据，输出一行：

Case #X: Y

其中 $X$ 表示测试用例编号，$Y$ 表示能够覆盖所有飞船的最小发射功率。若答案的相对或绝对误差不超过 $10^{-6}$，则视为正确。

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

Hint

样例解释

在第一个测试用例中，四艘飞船的坐标分别为 $(0, 0, 0), (1, 2, 0), (3, 4, 0), (2, 1, 0)$，接收功率均为 $1$。我们可以将巡洋舰放在 $(1.5, 2, 0)$，此时所需发射功率为 $3.5$，能够覆盖所有飞船。

在第二个测试用例中，我们可以将巡洋舰直接放在飞船上，所需发射功率为 $0$。

数据范围

• $1 \leq T \leq 10$
• $0 \leq x_i, y_i, z_i \leq 10^6$
• $1 \leq p_i \leq 10^6$

小数据范围（10 分，测试点 1 - 可见）

• $1 \leq N \leq 10$

大数据范围（20 分，测试点 2 - 隐藏）

• $1 \leq N \leq 1000$

由 ChatGPT 4.1 翻译