Placing a disk inside a polygon

Time Limit: 5 Seconds    Memory Limit: 65536 KB

A simple polygon is defined as a flat shape consisting of straight, non-intersecting line segments that are joined pair-wise to form a closed path. A simple polygon is called convex if for every pair of points within the polygon, every point on the straight line segment that joins them is also within the polygon. A disk can be placed inside a simple polygon if its center can be placed inside the simple polygon in such a way that the whole disk lies inside the polygon. You are responsible to compute the largest disk can be placed inside a convex polygon.

Input

There are multiple test cases.  The first line of each test case contains a single number n (at most 100) which is the number of vertices. Then n lines coming: the ith line contains the x and y coordinates of vertex vi  respectively separated with spaces. Both coordinates are real numbers with absolute value at most 10,000. The polygon is obtained by joining vi to vi+1 for all i from 1 to n (vn+1 = v1).The input terminates with a line containing 0.

Output

For each test case, the output is just a line as described next. If the polygon is not convex, output “Non convex polygon”. Otherwise, output the radius of the maximum disk can be placed inside the polygon with exactly two digits after the decimal point.

5
1.0 1.0
2.0 2.0
1.75 2.0
1.0 3.0
0.0 2.0
5
1.0 1.0
2.0 2.0
1.75 2.5
1.0 3.0
0.0 2.0
0

Sample Output

Non convex polygon
0.71
Submit

Source: 10th Iran Nationwide Internet Contest