#P18561. Circular Parterre
Circular Parterre
Circular Parterre
二维笛卡尔平面上有 个洒水器。每个洒水器都能浇到一个圆盘内部以及边界上的所有点。

你需要建造一个尽可能大的圆形花坛,使得花坛内部以及边界上的每一个点都能被至少一个洒水器浇到。求花坛的最大半径。
花坛可以由多个洒水器共同覆盖;它的整个闭圆盘必须包含在所有洒水圆盘的并集中。
输入格式
第一行一个整数 (),表示测试数据组数。对每组测试:
- 第一行一个整数 (),表示洒水器数量。
- 接下来 行,第 行三个整数 (,),表示第 个洒水器覆盖以 为圆心、 为半径的闭圆盘。
- 保证任意两个圆既不相同,也不相切(包含内切与外切)。
- 考虑任意两个圆之间的所有交点构成的多重集合,保证其中最近的点对距离不小于 。即使某个交点被其它圆盘覆盖,它也属于这个多重集合;不同圆对产生的交点不能重合。
保证所有测试组的 之和不超过 。
输出格式
对每组测试输出一行一个实数,表示最大圆形花坛的半径。
若你的输出为 ,标准答案为 ,当且仅当
时,答案被接受。也就是说,绝对误差或相对误差不超过 即可,等号也允许。
原样例
2
3
0 0 2
0 2 2
2 0 2
3
0 0 2
0 3 2
3 0 2
2.230710143300821420
2.000000000000000000