CF1446F.Line Distance

You are given an integer $k$ and $n$ distinct points with integer coordinates on the Euclidean plane, the $i$-th point has coordinates $(x_i, y_i)$.

Consider a list of all the $\frac{n(n - 1)}{2}$ pairs of points $((x_i, y_i), (x_j, y_j))$ ($1 \le i \lt j \le n$). For every such pair, write out the distance from the line through these two points to the origin $(0, 0)$.

Your goal is to calculate the $k$-th smallest number among these distances.

给你一个整数 $k$ 和平面上 $n$ 个互不相同的整数坐标点，其中第 $i$ 个点的坐标为 $(x_i, y_i)$。

考虑所有 $\frac{n(n - 1)}{2}$ 个点对 $((x_i, y_i), (x_j, y_j))$（其中 $1 \le i \lt j \le n$）构成的列表。对每个这样的点对，计算过这两点的直线到原点 $(0, 0)$ 的距离。

你的目标是计算这些距离中第 $k$ 小的数。

The first line contains two integers $n$, $k$ ($2 \le n \le 10^5$, $1 \le k \le \frac{n(n - 1)}{2}$).

The $i$-th of the next $n$ lines contains two integers $x_i$ and $y_i$ ($-10^4 \le x_i, y_i \le 10^4$) — the coordinates of the $i$-th point. It is guaranteed that all given points are pairwise distinct.

第一行包含两个整数 $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$ 个点的坐标。保证所有给定的点两两互不相同。

You should output one number — the $k$-th smallest distance from the origin. Your answer is considered correct if its absolute or relative error does not exceed $10^{-6}$.

Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is accepted if and only if $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$.

你应该输出一个数字——从原点出发的第 $k$ 小的距离。若你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

形式化地，设你的答案为 $a$，评测组的答案为 $b$。当且仅当 $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$ 时，你的答案被接受。

There are $6$ pairs of points:

• Line $1-2$ : distance $0$ from the origin
• Line $1-3$ : distance $\frac{\sqrt{2}}{2} \approx 0.707106781$ from the origin
• Line $1-4$ : distance $2$ from the origin
• Line $2-3$ : distance $1$ from the origin
• Line $2-4$ : distance $2$ from the origin
• Line $3-4$ : distance $\frac{2}{\sqrt{29}} \approx 0.371390676$ from the origin

The third smallest distance among those is approximately $0.707106781$.

共有 $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$

其中第三小的距离约为 $0.707106781$。