Description

In the Cartesian coordinate plane, there is a convex polygon with $N$ points. Now you want to place two circles with radius $R$ inside it, such that the two circles do not overlap. Find the maximum possible value of $R$.

Input Format

The first line contains an integer $N$.

The next $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$.

4
0 0
1 0
1 1
0 1

0.293 

4
0 0
3 0
3 1
0 1

0.500

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

2.189

Hint

Explanation for Sample 1

When the two circle centers are placed on the diagonal 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 the error between your answer and the standard answer does not exceed $0.001$, you will get AC.

Constraints and Limits

• For $10\%$ of the testdata, $N = 3$ is guaranteed.
• For $40\%$ of the testdata, $N \le 250$ is guaranteed.
• For $100\%$ of the testdata, $3 \le N \le 5\times 10^4$, $-10^7 \le x_i, y_i \le 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。

Translated by ChatGPT 5