AT_abc263_h.[ABC263Ex] Intersection 2

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

这些直线的交点（允许重复）共有 $\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}$，则视为正确。

限制条件

• $2 \leq N \leq 5 \times 10^4$
• $1 \leq K \leq \frac{N(N-1)}{2}$
• $-1000 \leq |A_i|, |B_i|, |C_i| \leq 1000 \ (1 \leq i \leq N)$
• 任意两条直线都不平行。
• $A_i \neq 0$ 或 $B_i \neq 0 \ (1 \leq i \leq N)$
• 输入均为整数。

样例解释 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}$。

由 ChatGPT 4.1 翻译