P13468 [GCJ 2008 #2] Star Wars

在遥远的银河系中，火星附近正爆发着帝国军与反叛军之间的殊死战斗。反叛军拥有 $N$ 艘飞船，我们将每艘飞船视为一个点 $(x_i, y_i, z_i)$。每艘飞船都配备了接收器，其接收功率为 $p_i$。反叛军需要能够从中央巡洋舰向所有飞船发送消息，但由于经费紧张，他们无法负担高功率的发射器。 如果巡洋舰被放置在 $(x, y, z)$，而另一艘飞船位于 $(x_i, y_i, z_i)$，其接收功率为 $p_i$，那么巡洋舰的发射器功率至少需要为： $$(|x_i - x| + |y_i - y| + |z_i - z|) / p_i$$ 你的任务是找到一个巡洋舰的位置，使得所需的发射器功率最小，并输出该最小功率。

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。 每组测试数据的第一行为整数 $N$，表示该组中飞船的数量。 接下来的 $N$ 行，每行包含四个整数 $x_i, y_i, z_i, p_i$，用空格分隔，分别表示第 $i$ 艘飞船的坐标和接收功率。可能有多艘飞船位于相同坐标。

对于每组输入数据，输出一行： Case #X: Y 其中 $X$ 表示测试用例编号，$Y$ 表示能够覆盖所有飞船的最小发射功率。若答案的相对或绝对误差不超过 $10^{-6}$，则视为正确。

**样例解释** 在第一个测试用例中，四艘飞船的坐标分别为 $(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 翻译