Two Circles in a Convex Polygon

You are given a convex polygon with $N$ vertices. Find the largest radius $R$ such that two circles of radius $R$ can both be placed entirely inside the polygon without overlapping (touching is allowed).

The first line contains the number of vertices $N$. Each of the next $N$ lines contains two integers $x_i$ and $y_i$, separated by a space, giving the coordinates of the $i$-th vertex.

Print the maximum radius $R$ on a single line, rounded to exactly three decimal places.

• $3 \le N \le 50000$
• $-10^7 \le x_i \le 10^7$
• $-10^7 \le y_i \le 10^7$
• The vertices are given in counter-clockwise (trigonometric) order.

For a square, the radius is maximised when the centres of the two circles lie on one of its diagonals. In that case the radius can be computed exactly as

$\dfrac{\sqrt{2}}{2,(1 + \sqrt{2})} \approx 0.293$