P13443 [GCJ 2009 #2] Watering Plants

在你的温室里，有若干株植物需要浇水。 每株植物占据一个圆形区域。任意两株植物不会重叠，也不会相互接触。 你打算购买两台喷洒器。每台喷洒器可以将半径为 $R$ 的圆形区域全部喷洒到水。 其中一台喷洒器将在早晨运行，另一台将在夜晚运行。为了让你满意，必须保证每株植物要么在早晨被完全浇水，要么在夜晚被完全浇水。也就是说，代表每株植物的圆形区域，必须被完全包含在两台喷洒器中的某一台（或两台）喷洒的圆形区域内。 给定每株植物的坐标和半径，请你求出能够放置两台喷洒器、使所有植物都被满足要求地浇水时，喷洒器所需的最小半径 $R$。喷洒器将被安装在天花板上，因此喷洒器的位置可以在植物的圆形区域内部。

- 第一行包含一个整数 $C$，表示测试用例的数量。 对于每个测试用例： - 第一行包含一个整数 $N$，表示植物的数量。 - 接下来 $N$ 行，每行包含三个整数 "$X\ Y\ R$"，表示一株植物的圆心坐标为 $(X, Y)$，半径为 $R$。

对于每个测试用例： - 输出一行，格式为 "Case #$x$: $R$"，其中 $x$ 是测试用例编号（从 1 开始），$R$ 是所需的最小喷洒器半径。 只要你的答案的绝对误差或相对误差不超过 $10^{-5}$，即可被接受。

**样例解释** 在第一个样例中，半径至少为 $7$ 且圆心在 $(20,15)$ 的喷洒器可以覆盖前两株植物。半径至少为 $3$ 的喷洒器可以覆盖位于 $(40,10)$ 的植物。 在第二个样例中，两台喷洒器中至少有一台的半径需要达到 $8$。注意，位于 $(30,10)$ 的植物必须被某一台喷洒器完全覆盖。 **限制条件** - $1 \leq X \leq 1000$ - $1 \leq Y \leq 1000$ - $1 \leq R \leq 100$ **小数据集（5 分）** - 时间限制：6 秒 - $1 \leq C \leq 10$ - $1 \leq N \leq 3$ **大数据集（25 分）** - 时间限制：12 秒 - $1 \leq C \leq 30$ - $1 \leq N \leq 40$ 翻译由 ChatGPT-4.1 完成。