#P18373. Iridescent Universe 2

Iridescent Universe 2

Iridescent Universe 2

题目描述

小青鱼居住在杯之宇宙中。这个宇宙里最大的行星 Rainow-Earth,是三维欧几里得空间中以 (0,0,0)(0,0,0) 为球心、半径为 rr 的球。

小鲮鱼经营着这个星球上的航空公司。球面上有 2n2n 座城市。对于每个 i=1,2,…,ni=1,2,\ldots,n,都有一条航线,沿着球面上的最短路线连接第 2i−12i-1 座城市和第 2i2i 座城市。

球面上两点之间的最短路线

图 1:球面上两点之间的最短路线。原图作者 CheCheDaWaff,来自 Wikimedia Commons,许可 CC BY-SA 4.0。

小青鱼准备建设一所名叫 Pretty Kind University 的大学。繁忙的航空交通使他很困扰,因此他希望大学尽可能远离噪声。

给定他的容忍程度 kk,请找出最大的实数 dd,使得存在一个球面上的建校位置,满足:在全部 nn 条航线中,到该位置的最小距离严格小于 dd 的航线至多有 kk 条。

一个位置到一条航线的最小距离,是该位置到航线上所有点的球面距离的最小值。

两点之间的距离,是球面上最短路线的长度,并非三维空间中的欧几里得距离。

球面距离与弦长的区别

图 2:PP 与 QQ 之间的距离是浅蓝色路线的长度,不是红色线段的长度。原图作者 PlatypeanArchcow,来自 Wikimedia Commons,许可 CC BY-SA 4.0。

输入格式

输入包含多组测试数据。第一行包含一个整数 TT(T≥1T\ge 1),表示测试数据组数。

对于每组测试数据:

第一行包含三个整数 n,k,rn,k,r,分别表示航线数量、小青鱼的容忍程度和星球半径,满足

1≤n≤100,0≤k<n,1≤r≤100.1\le n\le100,\qquad 0\le k<n,\qquad 1\le r\le100.

接下来 2n2n 行依次描述各座城市。其中第 ii 行包含三个整数 x,y,zx,y,z,满足

−100≤x,y,z≤100,x2+y2+z2>0.-100\le x,y,z\le100,\qquad x^2+y^2+z^2>0.

它们表示第 ii 座城市的实际坐标为

$$\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).$$

保证对于每个 i=1,2,…,ni=1,2,\ldots,n,第 2i−12i-1 座城市和第 2i2i 座城市既不重合,也不互为对跖点。因此,每条航线对应的球面最短路线都唯一确定。

保证同一个输入文件中,所有测试数据的 nn 之和不超过 100100。

输出格式

对于每组测试数据,输出一行,包含一个实数,表示最大的 dd。

你的答案的绝对误差或相对误差不超过 10−610^{-6} 即可。严格地说,设你的输出为 xx,评测答案为 yy,当且仅当

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

时,该答案被接受。

样例输入

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

样例说明

第一组测试数据的精确答案为 75π75\pi,第二组为 75π/275\pi/2,第三组为 75π75\pi。