Two Circles in a Convex Polygon

Time limit4sMemory limit128 MB

Summary

Find the largest radius R so that two non-overlapping circles of radius R fit inside a given convex polygon with N vertices.

Level: Hard9 of 10
Topics: Geometry, Binary search, Divide and conquer, Math
Solved: No attempts yet

Problem

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).

Input

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.

Output

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

Constraints

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

Hint

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$

Examples3

Example 1
Input
```
4
0 0
1 0
1 1
0 1
```
Expected output
```
0.293
```
Example 2
Input
```
4
0 0
3 0
3 1
0 1
```
Expected output
```
0.500
```
Example 3
Input
```
6
0 0
8 0
8 6
4 8
2 8
0 4
```
Expected output
```
2.189
```