查内克先生生活在一座以飞机为代表的城市中。他想建造一个半径为 $$$r$$$ 的圆形状的游乐园。圆必须接触原点(点 $$$(0, 0)$$$)。
公园里有$$$n$$$鸟类栖息地,可以成为游客拍照的地方。第 $$$i$$$ 个鸟类栖息地位于点 $$$p_i = (x_i, y_i)$$$。
找出公园内至少有 $$$k$$$ 鸟类栖息地的最小半径 $$$r$$$。
当且仅当 $$$p_i$$$ 与公园中心之间的距离小于或等于公园的半径时,该点才被视为位于公园内。请注意,公园的中心和半径不需要是整数。
在此问题中,保证给定的输入始终具有 $$$r \leq 2 \cdot 10^5$$$ 的解。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq k \leq n$$$) — 城市中鸟类栖息地的数量和公园内需要的鸟类栖息地的数量。
接下来的 $$$n$$$ 行的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$0 \leq |x_i|, |y_i| \leq 10^5$$$) — 第 $$$i$$$ 个鸟类栖息地的位置。
输出
输出一个实数 $$$r$$$ 表示内部至少有 $$$k$$$ 鸟类栖息地的公园的最小半径。保证给定的输入始终具有 $$$r \leq 2 \cdot 10^5$$$ 的解决方案。
如果您的答案的绝对或相对误差不超过 $$$10^{-4}$$$,则视为正确。
正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。当且仅当 $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}$$$ 时,您的答案才会被接受。
示例
输入 #1
8 4 -3 1 -4 4 1 5 2 2 2 -2 -2 -4 -1 -1 -6 0
输出 #1
3.1622776589
输入 #2
1 1 0 0
输出 #2
0.0000000000
注意
在第一个示例中,Chanek 先生可以将公园的中心放在 $$$(-3, -1)$$$ 处,半径为 $$$\sqrt{10} \approx 3.162$$$。可以证明这是最小值$$$r$$$。
下面说明第一个示例。蓝点代表鸟类栖息地,红圈代表游乐园。