Balkan Olympiad in Informatics: 2011 Day 1, Problem 1

We will consider a convex polygon with ~N~ vertices. We wish to find the maximum radius ~R~ such that two circles of radius ~R~ can be placed entirely inside the polygon without overlapping.

Input Specification

The first line of input contains the number ~N~. Each of the next ~N~ lines contains a pair of integers ~x_i~, ~y_i~ – representing the coordinates of the ~i~th point, separated by a space.

Output Specification

You should output a single number ~R~ – the desired radius. Output ~R~ with a precision of 3 decimals. You will pass a test if the output differs from the true answer by at most ~0.001~.

Constraints

• ~3 \le N \le 50\,000~
• ~-10^7 \le x_i \le 10^7~
• ~-10^7 \le y_i \le 10^7~
• The points are given in trigonometric (anti-clockwise) order.
• For ~10\%~ of tests ~N = 3~
• For ~40\%~ of tests ~N \le 250~

Sample Input 1

4
0 0
1 0
1 1
0 1

Sample Output 1

0.293

Explanation for Sample Output 1

The maximum radius is obtained when the centers of the two circles are placed on one of the square's diagonals. The radius can be calculated exactly and it is $$\displaystyle \frac{\sqrt{2}}{2(1+\sqrt{2})}\approx 0.293$$

Sample Input 2

4
0 0
3 0
3 1
0 1

Sample Output 2

0.500

Sample Input 3

6
0 0
8 0
8 6
4 8
2 8
0 4

Sample Output 3

2.189