Problem H - White Water Rafting
Time limit: 2 seconds
You have been hired by a big theme park to design a new attraction: a
white water rafting ride. You already designed the track; it is a round
trip that is described by an inner and an outer polygon. The space in
between the two polygons is the track.
You still need to design the rafts, however. It has been decided that
they should be circular, so that they can spin freely along the track and
increase the fun and excitement of the ride. Besides that, they should
be as big as possible to fit the maximum number of people, but they
can't be too big, for otherwise they would get stuck somewhere on the
track.
What is the maximum radius of the rafts so that they can complete the
track?
Input
On the first line one positive number: the number of testcases, at
most 100. After that per testcase:
- One line with an integer ni (3 ≤ ni ≤ 100): the number
of points of the inner polygon.
- ni lines with two integers each: the coordinates of the points
of the inner polygon in consecutive order.
- One line with an integer no (3 ≤ no &le 100): the number
of points of the outer polygon.
- no lines with two integers each: the coordinates of the points
of the outer polygon in consecutive order.
All coordinates have absolute value no larger than 1000. The
points of the polygons can be given in either clockwise or
counterclockwise order and the two polygons do not intersect or touch
themselves or each other. The outer polygon encloses the inner polygon.
Output
Per testcase:
- One line with a floating point number: the maximal radius of the
white water rafts. This number must have a relative or absolute error
less than 10-6.
Sample Input
2
4
-5 -5
5 -5
5 5
-5 5
4
-10 -10
-10 10
10 10
10 -10
3
0 0
1 0
1 1
5
3 -3
3 3
-4 2
-1 -1
-2 -2
Sample Output
2.5
0.70710678
The 2008 ACM Northwestern European Programming Contest