Problem I
Marshland Rescues
The Marshland Accident Prevention Syndicate (or MAPS for short) has just assumed stewardship of a newly discovered marshland. The marshland is made up of areas that are solid ground and areas that are water-logged. Each water-logged area can be modelled by a convex polygon, surrounded entirely by solid ground. Part of the responsibility of MAPS is rescuing any travellers who get stuck in any of the water-logged areas of the marshland. In order to prepare for future rescues, MAPS wants to know how far its first responders might have to wade into any water-logged area. Specifically, for each water-logged area, MAPS wishes to know the distance to any point that is furthest from solid ground, i.e., the greatest value $r$ such that there is a point $p$ inside the convex polygon such that the shortest distance from $p$ to the boundary of the polygon is $r$.
Input
The input consists of a single test case. The first line contains a single integer $n$, where $3\leq n\leq 10\, 000$, giving the number of vertices in the convex polygon modelling a water-logged area. Each of the next $n$ lines contains a pair of integers $x,y$ satisfying $-100\, 000\leq x,y\leq 100\, 000$ that are the coordinates of a vertex of the convex polygon. The vertices are given in counter-clockwise order, all vertices are distinct, and no 3 vertices are collinear.
Output
Output the greatest value $r$ such that there is a point $p$ inside the convex polygon such that the shortest distance from $p$ to the boundary of the polygon is $r$. Your answer must have an absolute or relative error of at most $10^{-6}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 2 0 6 0 8 3 3 5 0 2 |
2.300574391 |
