给你一个整数 $$$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}$$$ 时,您的答案才会被接受。
示例
输入 #1
4 3 2 1 -2 -1 0 -1 -2 4
输出 #1
0.707106780737
注意
有 $$$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$$$ 的距离