P15228 [SWERC 2017] Blowing Candles
题目描述
由于 Jacques-Édouard 非常喜欢生日蛋糕,他每小时庆祝一次生日,而不是每年一次。他的朋友们从一家著名的糕点店为他订购了一个圆形蛋糕,并在蛋糕顶部放置了蜡烛。蜡烛的数量等于 Jacques-Édouard 的年龄(以小时计)。因此,蛋糕顶部有大量燃烧的蜡烛。Jacques-Édouard 想一口气吹灭所有蜡烛。
你可以把蜡烛的火焰看作是在同一个平面上的点,所有这些点都在以原点为中心、半径为 $R$(纳米)的圆盘内。在同一平面上,Jacques-Édouard 吹出的空气轨迹可以用一个宽度为 $W$ 的直条带描述,该条带包括两条平行线之间距离为 $W$ 的区域,这两条线本身也包含在该区域内。求最小的宽度 $W$ ,使得如果 Jacques-Édouard 选择最佳的吹气方向,他可以吹灭所有蜡烛。
输入格式
第一行包含两个整数 $N$ 和 $R$ ,用空格分隔,其中 $N$ 是 Jacques-Édouard 的年龄(小时)。接下来 $N$ 行,每行包含两个整数 $x_i$ 和 $y_i$ ,表示第 $i$ 支蜡烛的坐标(纳米),用空格分隔。
输出格式
输出 $W$ 作为一个浮点数。允许 $10^{-5}$ 的绝对误差或相对误差:如果 $y$ 是答案,任何在 $[y - 10^{-5}; y + 10^{-5}]$ 区间内或在 $[(1 - 10^{-5})y; (1 + 10^{-5})y]$ 区间内的数都可以接受。
说明/提示
#### 样例解释
在样例中,三支蜡烛分别位于 $(0,0)$ 、 $(10,0)$ 和 $(0,10)$ 。最佳吹气方向对应的条带最小宽度约为 $7.0710678118654755$ ,使得所有点都在条带内或边界上。
### 数据范围
- $3 \leq N \leq 2 \cdot 10^5$ ;
- $10 \leq R \leq 2 \cdot 10^8$ ;
- 对于所有 $1 \leq i \leq N$ ,满足 $x_i^2 + y_i^2 \leq R^2$ ;
- 所有点的坐标互不相同。
翻译由 DeepSeek 完成