题目描述

$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}$ 以下であれば正解として扱われる。

题目大意

给定 $N$ 条不平行的直线 $A_ix+B_iy+C=0$，$N$ 条直线总共会有 $\frac{N(N-1)}{2}$ 个交点（包含在同一个位置的点，即相同位置算不同的点），找出距离原点第 $K$ 近的交点的距离。

翻译@Gemini7X

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

2.3570226040

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) $
• どの $2$ 本の直線も平行でない。
• $A_i\ \neq\ 0$ または $B_i\ \neq\ 0(1\ \le\ i\ \le\ N)$
• 入力は全て整数。

Sample Explanation 1

$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}$ です。