Placing a disk inside a polygon ACM 2012

Placing a disk inside a polygon

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 (Standard 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 (Standard 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.

Sample Input and Output

5

1.0 1.0

2.0 2.0

1.75 2.0

1.0 3.0

0.0 2.0

Non convex polygon


5

1.0 1.0

2.0 2.0

1.75 2.5

1.0 3.0

0.0 2.0

0.71

0

1 Like

Maybe these papers will help you (they deal, at least in part, with the problem of finding the largest circle inscribed in a convex polygon, which is exactly your problem):

Thanks for your help . I will take a look at them.
Thanks