分数: 600 点
问题陈述
有 N 二维平面中的线。的 i第行是 A_i x + B_i y + C_i = 0。保证没有两条线平行。
在这个平面上,有 \frac{N(N-1)}{2} 两条线的交点,包括重复项。打印原点和原点之间的距离 K- 其中距离原点最近的点 \frac{N(N-1)}{2} 点。
约束
- 2 \le N \le 5 \times 10^4
- 1 \le K \le \frac{N(N-1)}{2}
- -1000 \le |A_i|,|B_i|,|C_i| \le 1000(1 \le i \le N)
- 没有两条线是平行的。
- A_i \neq 0 or B_i \neq 0(1 \le i \le N).
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_N B_N C_N
输出
打印代表答案的实数。
当法官输出的绝对或相对误差最多为 10^{-4}.
示例输入 1
3 2 1 1 1 2 1 -3 1 -1 2
示例输出 1
2.3570226040
让我们调用 i第 行 行 i.
- 线的交点 1 和线 2 is (4,-5),其到原点的距离为 \sqrt{41} \simeq 6.4031242374.
- 线的交点 1 和线 3 is (\frac{-3}{2},\frac{1}{2}),其到原点的距离为 \frac{\sqrt{10}}{2} \simeq 1.5811388300.
- 线的交点 2 和线 3 is (\frac{1}{3},\frac{7}{3}),其到原点的距离为 \frac{5\sqrt{2}}{3} \simeq 2.3570226040.
因此,第二个最近的交点是 (\frac{1}{3},\frac{7}{3}),和 \frac{5\sqrt{2}}{3} 。
示例输入 2
6 7 5 1 9 4 4 -3 8 -1 2 0 1 -8 4 0 -4 2 -3 0
示例输出 2
4.0126752298