/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
xy 平面上に 2 直線 y=-100,\ y=100 で囲まれた通路があります。
この通路の中の -100 < x < 100 の部分に N 本の大きさの無視できる釘が打たれており、 i 本目の釘の座標は (x_i, y_i) です。
高橋くんは実数 r \ (0 < r \leq 100) を 1 つ選び、半径 r の円を中心が (-10^9, 0) に位置するように置きます。
その後、円を (-10^9, 0) から (10^9, 0) まで移動させます。
このとき、円は通路の境界や釘が円の内部に入らないような範囲で連続的に動かすことができるものとします。
円を (10^9, 0) まで動かせるような最大の r を求めてください。
制約
- 入力はすべて整数
- 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
出力
円を (10^9, 0) まで動かせるような最大の r を出力せよ。
なお、想定解答との絶対誤差または相対誤差が 10^{-4} 以下であれば正解として扱われる。
入力例 1
2 0 -40 0 40
出力例 1
40
r=40 の円を図のように y=0 に沿って動かすと、 (-10^9, 0) から (10^9, 0) まで移動させることができます。
x=0 のときにちょうど 2 つの点と接しますが、円の内部には入っていないため問題ありません。
r を 40 より大きくすると、円の中心を (10^9, 0) まで動かすことができなくなるため、 r=40 が最大になります。
入力例 2
4 0 -10 99 10 0 91 99 -91
出力例 2
50.5
入力例 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
10 65 -90 -34 -2 62 99 42 -13 47 -84 84 87 16 -78 56 35 90 8 90 19
出力例 4
35.003571246374276203
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