SP4585 GCJ08C - Star Wars

在一个遥远的星系中，火星附近，帝国舰队与反抗军正在进行一场殊死斗争。反抗军拥有 $N$ 艘战舰，我们将这些战舰看作点 $(x_i, y_i, z_i)$。每艘战舰都配备了功率为 $p_i$ 的接收器。为了实现从中央巡洋舰向所有战舰发送信息的目标，反抗军希望能够尽可能节省费用，因此他们无法购买价格昂贵的强力发射器。 假设巡洋舰的位置是 $(x, y, z)$，而某一艘战舰位于 $(x_i, y_i, z_i)$，其接收器功率为 $p_i$，那么巡洋舰的发射功率至少需要满足： $$ \frac{|x_i - x| + |y_i - y| + |z_i - z|}{p_i} $$ 你的任务是找出巡洋舰的位置，使其所需的发射功率最小，并输出这个最小功率。

第一行输入一个整数 $T$，表示测试用例的数量。接下来有 $T$ 组测试用例。 每个测试用例第一行给出整数 $N$，表示战舰的数量。 接下来的 $N$ 行中，每一行包含四个整数 $x_i, y_i, z_i$ 和 $p_i$，用空格隔开，分别表示第 $i$ 艘战舰的坐标和接收器的功率。可能存在多艘战舰位于同一坐标。 $$ 1 \leq T \leq 20 $$ $$ 0 \leq x_i, y_i, z_i \leq 10^6 $$ $$ 1 \leq p_i \leq 10^6 $$ $$ 1 \leq N \leq 1000 $$

对于每个测试用例，输出如下格式： ``` Case #X: Y ``` 其中 $X$ 表示测试用例的编号，$Y$ 为满足到达所有战舰所需的最小功率。答案允许有不超过 $10^{-6}$ 的相对或绝对误差。 **本翻译由 AI 自动生成**