CF1446F Line Distance

给定一个整数 $k$ 和 $n$ 个在欧几里得平面上的不同整点，第 $i$ 个点的坐标为 $(x_i, y_i)$。 考虑所有 $\frac{n(n - 1)}{2}$ 对点 $((x_i, y_i), (x_j, y_j))$（$1 \le i < j \le n$）。对于每一对点，写出经过这两点的直线到原点 $(0, 0)$ 的距离。 你的目标是计算这些距离中第 $k$ 小的数。

第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 10^5$，$1 \le k \le \frac{n(n - 1)}{2}$）。 接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$-10^4 \le x_i, y_i \le 10^4$），表示第 $i$ 个点的坐标。保证所有点两两不同。

输出一个数，表示第 $k$ 小的原点到直线的距离。如果你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。 形式化地，设你的答案为 $a$，标准答案为 $b$。当且仅当 $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$ 时，你的答案被接受。

共有 $6$ 对点： - 直线 $1-2$：到原点的距离为 $0$ - 直线 $1-3$：到原点的距离为 $\frac{\sqrt{2}}{2} \approx 0.707106781$ - 直线 $1-4$：到原点的距离为 $2$ - 直线 $2-3$：到原点的距离为 $1$ - 直线 $2-4$：到原点的距离为 $2$ - 直线 $3-4$：到原点的距离为 $\frac{2}{\sqrt{29}} \approx 0.371390676$ 这些距离中第 $3$ 小的约为 $0.707106781$。 由 ChatGPT 4.1 翻译