当前没有测试数据。

Ex - 相交 2

得分：600 分

问题描述

平面上有 $N$ 条直线。第 $i$ 条直线表示为 $A_i x + B_i y + C_i = 0$。保证没有两条直线是平行的。

在这个平面上，有 $\frac{N(N-1)}{2}$ 个两两相交的点，包括重复的点。输出距离原点最近的第 $K$ 个相交点到原点的距离。

约束条件

• $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$ 要么 $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}$ 时，你的输出被认为是正确的。

3 2
1 1 1
2 1 -3
1 -1 2

2.3570226040

把第 $i$ 条直线称为直线 $i$。

• 直线 $1$ 和直线 $2$ 的交点是 $(4,-5)$，距离原点的距离为 $\sqrt{41} \simeq 6.4031242374$。
• 直线 $1$ 和直线 $3$ 的交点是 $(\frac{-3}{2},\frac{1}{2})$，距离原点的距离为 $\frac{\sqrt{10}}{2} \simeq 1.5811388300$。
• 直线 $2$ 和直线 $3$ 的交点是 $(\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}$。

6 7
5 1 9
4 4 -3
8 -1 2
0 1 -8
4 0 -4
2 -3 0

4.0126752298