#P18561. Circular Parterre

Circular Parterre

Circular Parterre

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

图9:两个原样例中的最大圆形花坛

你需要建造一个尽可能大的圆形花坛,使得花坛内部以及边界上的每一个点都能被至少一个洒水器浇到。求花坛的最大半径。

花坛可以由多个洒水器共同覆盖;它的整个闭圆盘必须包含在所有洒水圆盘的并集中。

输入格式

第一行一个整数 TT(1≤T≤3001\le T\le300),表示测试数据组数。对每组测试:

  • 第一行一个整数 nn(1≤n≤3001\le n\le300),表示洒水器数量。
  • 接下来 nn 行,第 ii 行三个整数 xi,yi,rix_i,y_i,r_i(−1000≤xi,yi≤1000-1000\le x_i,y_i\le1000,1≤ri≤10001\le r_i\le1000),表示第 ii 个洒水器覆盖以 (xi,yi)(x_i,y_i) 为圆心、rir_i 为半径的闭圆盘。
  • 保证任意两个圆既不相同,也不相切(包含内切与外切)。
  • 考虑任意两个圆之间的所有交点构成的多重集合,保证其中最近的点对距离不小于 0.010.01。即使某个交点被其它圆盘覆盖,它也属于这个多重集合;不同圆对产生的交点不能重合。

保证所有测试组的 nn 之和不超过 300300。

输出格式

对每组测试输出一行一个实数,表示最大圆形花坛的半径。

若你的输出为 xx,标准答案为 yy,当且仅当

∣x−y∣max⁡(1,∣y∣)≤10−6\frac{|x-y|}{\max(1,|y|)}\le10^{-6}

时,答案被接受。也就是说,绝对误差或相对误差不超过 10−610^{-6} 即可,等号也允许。

原样例

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