#P18373. Iridescent Universe 2
Iridescent Universe 2
Iridescent Universe 2
题目描述
小青鱼居住在杯之宇宙中。这个宇宙里最大的行星 Rainow-Earth,是三维欧几里得空间中以 为球心、半径为 的球。
小鲮鱼经营着这个星球上的航空公司。球面上有 座城市。对于每个 ,都有一条航线,沿着球面上的最短路线连接第 座城市和第 座城市。

图 1:球面上两点之间的最短路线。原图作者 CheCheDaWaff,来自 Wikimedia Commons,许可 CC BY-SA 4.0。
小青鱼准备建设一所名叫 Pretty Kind University 的大学。繁忙的航空交通使他很困扰,因此他希望大学尽可能远离噪声。
给定他的容忍程度 ,请找出最大的实数 ,使得存在一个球面上的建校位置,满足:在全部 条航线中,到该位置的最小距离严格小于 的航线至多有 条。
一个位置到一条航线的最小距离,是该位置到航线上所有点的球面距离的最小值。
两点之间的距离,是球面上最短路线的长度,并非三维空间中的欧几里得距离。

图 2: 与 之间的距离是浅蓝色路线的长度,不是红色线段的长度。原图作者 PlatypeanArchcow,来自 Wikimedia Commons,许可 CC BY-SA 4.0。
输入格式
输入包含多组测试数据。第一行包含一个整数 (),表示测试数据组数。
对于每组测试数据:
第一行包含三个整数 ,分别表示航线数量、小青鱼的容忍程度和星球半径,满足
接下来 行依次描述各座城市。其中第 行包含三个整数 ,满足
它们表示第 座城市的实际坐标为
$$\left(\frac{rx}{\sqrt{x^2+y^2+z^2}},\ \frac{ry}{\sqrt{x^2+y^2+z^2}},\ \frac{rz}{\sqrt{x^2+y^2+z^2}}\right).$$保证对于每个 ,第 座城市和第 座城市既不重合,也不互为对跖点。因此,每条航线对应的球面最短路线都唯一确定。
保证同一个输入文件中,所有测试数据的 之和不超过 。
输出格式
对于每组测试数据,输出一行,包含一个实数,表示最大的 。
你的答案的绝对误差或相对误差不超过 即可。严格地说,设你的输出为 ,评测答案为 ,当且仅当
时,该答案被接受。
样例输入
3
1 0 100
0 0 1
0 1 0
2 0 100
1 1 0
1 -1 0
-1 0 1
-1 0 -1
2 1 100
1 1 0
1 -1 0
-1 0 1
-1 0 -1
样例输出
235.619449019234
117.809724509617
235.619449019234
样例说明
第一组测试数据的精确答案为 ,第二组为 ,第三组为 。