交点 2

题目描述

在二维平面上有 $N$ 条直线。第 $i$ 条直线为 $A_i x + B_i y + C_i = 0$。保证任意 $2$ 条直线不平行。

这些直线的交点共有 $\frac{N(N-1)}{2}$ 个(包含重复),求其中距离原点第 $K$ 近的点到原点的距离。

输入格式

$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$。

因此,距离原点第 $2$ 近的点是 $(\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

数据范围

• $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)$。
• 所有输入都是整数。