F - 银树林

分数：600分

问题描述

在 $xy$ 平面上，有一个被 $y=-100$ 和 $y=100$ 两条直线包围的通道。

在 $-100 < x < 100$ 的通道部分，有 $N$ 个微小的钉子。第 $i$ 个钉子的坐标为 $(x_i, y_i)$。

高桥将选择一个实数 $r \ (0 < r \leq 100)$，并将一个半径为 $r$ 的圆放置在 $(-10^9, 0)$ 处，以此为圆心。

然后，他将把圆从 $(-10^9, 0)$ 移动到 $(10^9, 0)$。

在此过程中，他连续移动圆(路径随意)，使通道的边界或者钉子的部分不穿透圆的内部。

请找到最大可能的 $r$ 值，使得能够将圆移动到 $(10^9, 0)$。

约束

• 输入中的所有值均为整数。
• $1 \leq N \leq 100$
• $|x_i|, |y_i| < 100$
• 对于 $i \neq j$，$(x_i, y_i) \neq (x_j, y_j)$。

输入

输入以以下格式从标准输入中给出：

$N$

$x_1$ $y_1$

$\vdots$

$x_N$ $y_N$

输出

输出最大可能的 $r$ 值，使得能够将圆移动到 $(10^9, 0)$。 如果你的输出与我们的答案的绝对或相对误差最多为 $10^{-4}$，则输出被认为是正确的。

2
0 -40
0 40

40

如图所示，我们可以将半径为 $r=40$ 的圆从 $(-10^9, 0)$ 沿 $y=0$ 移动到 $(10^9, 0)$。

当 $x=0$ 时，圆正好触及两个钉子，这是可以接受的，因为它们不穿透圆的内部。

任何大于 $40$ 的 $r$ 值都使得将圆移动到 $(10^9, 0)$ 成为不可能，所以最大可能的值为 $r=40$。

4
0 -10
99 10
0 91
99 -91

50.5

10
-90 40
20 -30
0 -90
10 -70
80 70
-90 30
-20 -80
10 90
50 30
60 -70

33.541019662496845446

10
65 -90
-34 -2
62 99
42 -13
47 -84
84 87
16 -78
56 35
90 8
90 19

35.003571246374276203