配点 : $600$ 点

問題文

$2$ 次元平面上に $N$ 本の直線があります。$i$ 本目の直線は $A_i x + B_i y + C_i = 0$ です。どの $2$ 本の直線も平行でないことが保証されます。

これらの直線の交点は、重複ありで $\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)$
• どの $2$ 本の直線も平行でない。
• $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$ です。

よって、$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