P17403 [ICPC 2018 Shenyang R] Machining Disc Rotors

爱德华是铝循环机械公司的一名工人。他的工作是控制机械臂来切除模具材料的一些部分。以下是对他工作的简要介绍。 假设他的操作面板是一个带有坐标系的欧几里得平面。初始时，模具是一个圆心坐标为 $(0, 0)$、半径为 $R$ 的圆盘。爱德华控制 $n$ 个不同的机械臂，将它们各自影响区域内的所有模具切除并抹去。第 $i$ 个机械臂的影响区域是一个圆心坐标为 $(x_i, y_i)$、半径为 $r_i$ 的圆。为了获得高度精良的产品，保证任意两个机械臂的影响区域互不相交，并且没有一个影响区域完全包含整个原始模具。 你的任务是确定残余模具的直径。这里，欧几里得平面上一个子集（可能非凸）的直径是指该子集中任意两点间距离的上确界（即最小上界）。样例的图示如下。 :::align{center}  :::

输入包含多组测试数据，第一行包含一个正整数 $T$，表示测试数据的组数，最多不超过 $5000$。 对于每组测试数据，第一行包含两个整数 $n$ 和 $R$，满足 $1 \le n \le 100$，$1 \le R \le 1000$。 接下来的 $n$ 行描述爱德华控制的所有机械臂，第 $i$ 行包含三个整数 $x_i$、$y_i$ 和 $r_i$，描述第 $i$ 个机械臂的影响区域，其中 $-1000 \le x_i, y_i \le 1000$，$1 \le r_i \le 1000$。

对于每组测试数据，输出一行 `"Case #x: y"`（不含引号），其中 $x$ 是测试数据编号（从 $1$ 开始），$y$ 是剩余区域的直径，绝对误差或相对误差不超过 $10^{-9}$。准确来说，设你的答案为 $a$，裁判答案为 $b$，如果 $\frac{|a - b|}{\max \lbrace 1, |b| \rbrace} \le 10^{-9}$，则你的答案被视为正确，其中 $\max \lbrace x, y \rbrace$ 表示 $x$ 和 $y$ 的最大值，$|x|$ 表示 $x$ 的绝对值。

在样例中，剩余区域的直径为 $\sqrt{324 + \frac{162 \sqrt{471}}{157}} \approx 18.611654895000253$，这等于点 $(-8, 6)$ 与 $\left(\frac{11}{2} - \frac{27 \sqrt{471}}{157}, -3 - \frac{99 \sqrt{471}}{314}\right)$ 之间的距离。 翻译由 DeepSeek V4 Pro 完成