 Mount Allison Programming Showdown 2019

#### Start

2019-03-16 08:00 AKDT

## Mount Allison Programming Showdown 2019

#### End

2019-03-16 13:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -552 days 16:14:06

5:00:00

0:00:00

# Problem IMarshland 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