Problem Description

On a plane with a Cartesian coordinate system, there is a convex polygon containing $N$ points. We want to place two circles with radius $R$ inside it such that the circles do not overlap. Determine the maximum value of $R$.

Input Format

The first line contains an integer $N$.

The following $N$ lines each contain two integers $x_i, y_i$, representing the coordinates of the $i$-th point of the polygon.

Output Format

Output a single real number $R$.

Sample Input and Output

Sample Input #1

4
0 0
1 0
1 1
0 1

Sample Output #1

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

Notes

Sample 1 Explanation

When the centers of the two circles are placed on the diagonals of the square, the radius is maximized, as shown in the figure:

The radius is $\frac{\sqrt{2}}{2\times (1+\sqrt{2})} \approx 0.293$.

SPJ Scoring Criteria

If your answer is within an error margin of $0.001$ from the standard answer, you will receive AC.

Data Range and Constraints

• For $10\%$ of the data, $N = 3$ is guaranteed.
• For $40\%$ of the data, $N \leq 250$ is guaranteed.
• For $100\%$ of the data, $3 \leq N \leq 5 \times 10^4$, $-10^7 \leq x_i, y_i \leq 10^7$, and the points are given in counterclockwise order.

Note

This problem is translated from Balkan Olympiad in Informatics 2011 Day 1 T1 2circles.

见题面 Input 部分

见题面 Output 部分