经过一场旷日持久的摩尔清晰军备竞赛,农夫约翰和顽皮的混乱制造者终于同意建立和平。他们计划用一条穿过散布在这片土地上的 n 个前哨站中至少两个的线来划分玻维尼亚的领土。这些前哨站是冲突的残余,位于 (x1, y1)、(x2, y2)、...、(xn, yn) 点。
为了找到最佳分界线,Farmer John 和 Elsie 在坐标平面上绘制了玻维尼亚地图。农夫约翰的农场和顽皮混乱制造者的基地分别位于点 P = (a, 0) 和 Q = ( - a, 0) 处。因为他们寻求持久的和平,农夫约翰和埃尔西希望最小化直线上任意点到 P 和 Q 的距离之间的最大差异。
正式地,将线 $$e$$ 相对于两点 P 和 Q 的差定义为最小实数 d,这样对于线 $$e$$ 上的所有点 X,|PX - QX| ≤ d。 (保证 d 存在并且是唯一的。)他们希望找到穿过两个不同前哨站 (xi, yi) 和 (xj, yj) 的线 $$e$$,使得 $$e$$ 相对于 P 和 Q 的差异最小化。
输入
输入的第一行包含两个整数 n 和 a (2 ≤ n ≤ 100 000, 1 ≤ a ≤ 10 000)——分别是前哨站的数量以及农场和基地的坐标。
以下 n 行将前哨站的位置描述为整数对 (xi, yi) (|xi|, |yi| ≤ 10 000)。这些点彼此不同,也与 P 和 Q 不同。
输出
打印单个实数——最佳分割线的差值。如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。
即:假设你的答案是a,陪审团的答案是b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$,检查程序将认为您的答案正确。
示例
输入 #1
2 5 1 0 2 1
输出 #1
7.2111025509
输入 #2
3 6 0 1 2 5 0 -3
输出 #2
0.0000000000
注意
在第一个示例中,唯一可能的线 $$e$$ 是 y = x - 1。可以证明,最大化 |PX - QX| 的点 X是 (13, 12),其中 $$| PX-QX| = | \sqrt { ( 1 3 - 5 ) ^ { 2 } + ( 1 2 - 0 ) ^ { 2 } } - \sqrt { ( 1 3 - ( - 5 ) ) ^ { 2 } + ( 1 2 - 0 ) ^ { 2 } } |$$,即 $$2\sqrt{13} \approx 7.211025509$$。
在第二个示例中,如果我们选择点 (0, 1) 和 (0, - 3),则当 x = 0 时,我们会得到 $$e$$。因为在这条线上 PX = QX,所以最小可能差值为 0。