102637: [AtCoder]ABC263 Ex - Intersection 2

Problem Statement

There are $N$ lines in a two-dimensional plane. The $i$-th line is $A_i x + B_i y + C_i = 0$. It is guaranteed that no two of the lines are parallel.

In this plane, there are $\frac{N(N-1)}{2}$ intersection points of two lines, including duplicates. Print the distance between the origin and the $K$-th nearest point to the origin among these $\frac{N(N-1)}{2}$ points.

Constraints

• $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)$
• No two of the lines are parallel.
• $A_i \neq 0$ or $B_i \neq 0(1 \le i \le N)$.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $K$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_N$ $B_N$ $C_N$

Output

Print a real number representing the answer.

Your output is considered correct when its absolute or relative error from the judge's output is at most $10^{-4}$.

Sample Input 1

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

Sample Output 1

2.3570226040

Let us call the $i$-th line Line $i$.

• The intersection point of Line $1$ and Line $2$ is $(4,-5)$, whose distance to the origin is $\sqrt{41} \simeq 6.4031242374$.
• The intersection point of Line $1$ and Line $3$ is $(\frac{-3}{2},\frac{1}{2})$, whose distance to the origin is $\frac{\sqrt{10}}{2} \simeq 1.5811388300$.
• The intersection point of Line $2$ and Line $3$ is $(\frac{1}{3},\frac{7}{3})$, whose distance to the origin is $\frac{5\sqrt{2}}{3} \simeq 2.3570226040$.

Therefore, the second nearest intersection point is $(\frac{1}{3},\frac{7}{3})$, and $\frac{5\sqrt{2}}{3}$ should be printed.

Sample Input 2

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

Sample Output 2

4.0126752298

问题描述

在一个二维平面上有$N$条线。第$i$条线是$A_i x + B_i y + C_i = 0$。可以保证没有两条线是平行的。

在这个平面上，有$\frac{N(N-1)}{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)$
• 没有两条线是平行的。
• $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}$时，你的输出被认为是正确的。

样例输入1

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

样例输出1

2.3570226040

让我们称第$i$条线为Line $i$。

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

样例输入2

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

样例输出2

4.0126752298