← 返回题目列表

Codeforces · 1575/B

B. 建造游乐园

中文机器翻译题面 查看原题

查内克先生生活在一座以飞机为代表的城市中。他想建造一个半径为 $$$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$$$。

下面说明第一个示例。蓝点代表鸟类栖息地,红圈代表游乐园。