Mount Allison Programming Showdown 2019

Start

2019-03-16 16:00 UTC

Mount Allison Programming Showdown 2019

End

2019-03-16 21:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -219 days 13:44:35

Time elapsed

5:00:00

Time remaining

0:00:00

Problem I
Marshland Rescues

/problems/marshlandrescues/file/statement/en/img-0001.jpg
Image by scanrail (123RF), Used under license

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