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}$，则视为正确。

输入输出样例 #1

输入 #1

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

输出 #1

2.3570226040

输入输出样例 #2

输入 #2

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

输出 #2

4.0126752298

说明/提示

限制条件

• $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 翻译