Description

在你的温室里，有若干株植物需要浇水。

每株植物占据一个圆形区域。任意两株植物不会重叠，也不会相互接触。

你打算购买两台喷洒器。每台喷洒器可以将半径为 $R$ 的圆形区域全部喷洒到水。

其中一台喷洒器将在早晨运行，另一台将在夜晚运行。为了让你满意，必须保证每株植物要么在早晨被完全浇水，要么在夜晚被完全浇水。也就是说，代表每株植物的圆形区域，必须被完全包含在两台喷洒器中的某一台（或两台）喷洒的圆形区域内。

给定每株植物的坐标和半径，请你求出能够放置两台喷洒器、使所有植物都被满足要求地浇水时，喷洒器所需的最小半径 $R$。喷洒器将被安装在天花板上，因此喷洒器的位置可以在植物的圆形区域内部。

Input Format

• 第一行包含一个整数 $C$，表示测试用例的数量。

对于每个测试用例：

• 第一行包含一个整数 $N$，表示植物的数量。
• 接下来 $N$ 行，每行包含三个整数 "$X\ Y\ R$"，表示一株植物的圆心坐标为 $(X, Y)$，半径为 $R$。

Output Format

对于每个测试用例：

• 输出一行，格式为 "Case #$x$: $R$"，其中 $x$ 是测试用例编号（从 1 开始），$R$ 是所需的最小喷洒器半径。

只要你的答案的绝对误差或相对误差不超过 $10^{-5}$，即可被接受。

2
3
20 10 2
20 20 2
40 10 3
3
20 10 3
30 10 3
40 10 3

Case #1: 7.000000
Case #2: 8.000000

Hint

样例解释

在第一个样例中，半径至少为 $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 完成。