AT_abc181_f [ABC181F] Silver Woods

题目描述

在 $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)$。

在移动过程中，圆必须始终保持在通道内，且不能让任何钉子进入圆的内部（可以与钉子相切）。

请你求出能够将圆移动到 $(10^9, 0)$ 的最大半径 $r$。

输入格式

输入通过标准输入给出，格式如下：

$N$
$x_1\ y_1$
$x_2\ y_2$
$\vdots$
$x_N\ y_N$

输出格式

输出能够将圆移动到 $(10^9, 0)$ 的最大半径 $r$。
如果你的输出与标准答案的绝对误差或相对误差在 $10^{-4}$ 以内，则视为正确。

输入输出样例 #1

输入 #1

2
0 -40
0 40

输出 #1

40

输入输出样例 #2

输入 #2

4
0 -10
99 10
0 91
99 -91

输出 #2

50.5

输入输出样例 #3

输入 #3

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

输出 #3

33.541019662496845446

输入输出样例 #4

输入 #4

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

输出 #4

35.003571246374276203

说明/提示

限制条件

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

样例解释 1

如图所示，当 $r=40$ 时，可以沿 $y=0$ 将圆从 $(-10^9, 0)$ 移动到 $(10^9, 0)$。在 $x=0$ 时，圆恰好与两个点相切，但没有包含它们在内部，因此没有问题。如果 $r$ 大于 $40$，则无法将圆的圆心移动到 $(10^9, 0)$，因此最大半径为 $r=40$。

由 ChatGPT 4.1 翻译