题目描述

爱德华是铝循环机械公司的一名工人。他的工作是控制机械臂来切除模具材料的一些部分。以下是对他工作的简要介绍。

假设他的操作面板是一个带有坐标系的欧几里得平面。初始时，模具是一个圆心坐标为 $(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$ 的绝对值。

1
3 10
0 12 10
11 -6 10
-11 -6 10

Case #1: 18.611654895000252

提示

在样例中，剩余区域的直径为 $\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 完成