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 50000$
• $-{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\mathrm{\%}$ of tests $N=3$
• For $40\mathrm{\%}$ 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