101815: [AtCoder]ABC181 F - Silver Woods

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $600$ points

Problem Statement

On the $xy$-plane, we have a passage surrounded by the two lines $y=-100$ and $y=100$.

In the part of this passage with $-100 < x < 100$, there are $N$ negligibly small nails. The coordinates of the $i$-th nail are $(x_i, y_i)$.

Takahashi will choose a real number $r \ (0 < r \leq 100)$ and put a circle of radius $r$ so that its center is at $(-10^9, 0)$.

Then, he will move the circle from $(-10^9, 0)$ to $(10^9, 0)$.

Here, he continuously moves the circle so that the boundaries of the passage or the nails do not penetrate the interior of the circle.

Find the maximum possible value of $r$ such that it is possible to move the circle to $(10^9, 0)$.

Constraints

  • All values in input are integers.
  • $1 \leq N \leq 100$
  • $|x_i|, |y_i| < 100$
  • If $i \neq j$, $(x_i, y_i) \neq (x_j, y_j)$.

Input

Input is given from Standard Input in the following format:

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

Output

Print the maximum possible value of $r$ such that it is possible to move the circle to $(10^9, 0)$. Your output will be considered correct when its absolute or relative error from our answer is at most $10^{-4}$.


Sample Input 1

2
0 -40
0 40

Sample Output 1

40

As shown in the figure, we can move the circle with $r=40$ from $(-10^9, 0)$ to $(10^9, 0)$ by moving it along $y=0$.

When $x=0$, the circle exactly touches the two nails, which is fine since they do not penetrate the interior of the circle.

Any value of $r$ greater than $40$ makes it impossible to move the circle to $(10^9, 0)$, so the maximum possible value is $r=40$.


Sample Input 2

4
0 -10
99 10
0 91
99 -91

Sample Output 2

50.5

Sample Input 3

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

Sample Output 3

33.541019662496845446

Sample Input 4

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

Sample Output 4

35.003571246374276203

Input

题意翻译

给你一个平面,上界是直线 $y=100$ 下界是直线 $y=-100$。 在平面上 $n$ 个钉子,钉子不能在圆内。 一个圆从 $x=-\infty$ 开始向右运动,问最大的半径使圆能够到达 $x=\infty$。

加入题单

上一题 下一题 算法标签: