CF645G Armistice Area Apportionment

在一场旷日持久的“核”军备竞赛后，Farmer John 和 Mischievous Mess Makers 终于决定缔结和平。他们计划用一条经过至少 $n$ 个散布在土地上的前哨站中的任意两个的直线，将 Bovinia 的领土划分开。这些前哨站是冲突留下的遗迹，分别位于点 $(x_{1},y_{1}),(x_{2},y_{2}),\ldots,(x_{n},y_{n})$。 为了寻找最佳的分界线，Farmer John 和 Elsie 在坐标平面上绘制了 Bovinia 的地图。Farmer John 的农场和 Mischievous Mess Makers 的基地分别位于点 $P=(a,0)$ 和 $Q=(-a,0)$。因为他们希望建立持久的和平，Farmer John 和 Elsie 想要使任何直线上点到 $P$ 和 $Q$ 距离差的最大值尽可能小。 更正式地，定义一条直线相对于点 $P$ 和 $Q$ 的“差”为最小实数 $d$，使得对于直线上的任意点 $X$，$|PX - QX| \leq d$。（保证 $d$ 存在且唯一。）他们希望找到一条经过两个不同前哨站 $(x_i, y_i)$ 和 $(x_j, y_j)$ 的直线，使得该直线相对于 $P$ 和 $Q$ 的“差”最小。

输入的第一行包含两个整数 $n$ 和 $a$（$2 \leq n \leq 100000$，$1 \leq a \leq 10000$）——表示前哨站的数量以及农场和基地的位置。 接下来的 $n$ 行每行包含一对整数 $(x_i, y_i)$（$|x_i|,|y_i|\leq 10000$），表示每个前哨站的位置。这些点彼此之间不同，也不会与 $P$ 或 $Q$ 重合。

输出一个实数，即最优分界线的“差”。如果你的绝对误差或相对误差不超过 $10^{-6}$，则认为是正确答案。 即，假设你的答案为 $a$，评测的标准答案为 $b$。如果 $\frac{|a-b|}{\max(1,|b|)} \leq 10^{-6}$ ，则答案正确。

在第一个样例中，唯一可能的直线是 $y=x-1$。可以证明使 $|PX-QX|$ 达到最大值的点为 $(13,12)$，此时 $|PX-QX| = \sqrt{(13-a)^2+12^2} - \sqrt{(13+a)^2+12^2} \approx 1.9999948$。 在第二个样例中，如果选择点 $(0, 1)$ 和 $(0, -3)$，则这条直线为 $x=0$。因为在这条直线上 $PX=QX$，所以最小“差”为 $0$。 由 ChatGPT 5 翻译