← 返回题目列表

Codeforces · 1190/E

E. 时风和爆炸

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

时风和她的朋友们正试图潜入克拉丽斯建造的秘密基地。然而,克拉丽丝已经意识到了这一点,并设置了一颗炸弹,炸弹在一分钟内就会爆炸。尽管他们试图逃跑,但发现门被锁后,他们无处可去。

就在这时,时风之父CJB来了。凭借冥界女神埃列什基伽勒赋予的魔力,CJB 能够设置 $$$m$$$ 屏障来保护他们免受爆炸的伤害。正式地,我们在平面上建立一个笛卡尔坐标系,并假设炸弹位于 $$$O(0, 0)$$$。时风的船员中有$$$n$$$人,其中第$$$i$$$人位于$$$P_i(X_i, Y_i)$$$。每个障碍都可以被视为一条无限长的线,并且它们可以相互相交。对于时风船员中的每个人来说,必须有至少一个屏障将炸弹和他分开,这意味着炸弹和他之间的线与至少一个屏障相交。在这个定义中,如果有人站在炸弹的位置,任何经过 $$$O(0, 0)$$$ 的线都满足要求。

虽然CJB很强大,但他还是希望自己的屏障离炸弹越远越好,以节省体力。请帮助他计算炸弹和最近的障碍物之间的最大距离,同时时风的所有船员都安全。

输入

第一行包含两个整数$$$n$$$、$$$m$$$ ($$$1 \leq n, m \leq 10^5$$$),分别表示人数和障碍物数量。

接下来$$$n$$$行中的第$$$i$$$行包含两个整数$$$X_i$$$、$$$Y_i$$$ ($$$-10^5 \leq X_i, Y_i \leq 10^5$$$),表示第$$$i$$$人的位置$$$P_i(X_i, Y_i)$$$。请注意,$$$P_i$$$ 可能与 $$$P_j$$$ ($$$j \neq i$$$) 甚至 $$$O$$$ 具有相同的坐标。

输出

打印单个实数——满足要求的最大距离。如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。

正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。当且仅当 $$$\frac{|a - b|}{\max(1, |b|)} \leq 10^{-6}$$$ 时,您的答案才会被接受。

示例

输入 #1

3 1
2 0
0 2
-1 0

输出 #1

0.0000000000

输入 #2

1 1
0 0

输出 #2

0.0000000000

输入 #3

2 1
-1 -1
-1 -1

输出 #3

1.4142135617

输入#4

3 100000
3 2
-1 -3
2 -5

输出#4

3.1622776602

注意

在前两个示例中,CJB 必须设置跨越 $$$O(0, 0)$$$ 的障碍。

在最后两个示例中,CJB 可以设置跨越某个 $$$P_i$$$ 的每个障碍,使得障碍垂直于 $$$P_i$$$ 和 $$$O$$$ 之间的线。