SP7589 PC8C - Cave Crisis

R2D2 was exploring a tunnel when a cave-in suddenly occurred. Oh no, is he trapped? 

The input file will contain multiple test cases. Each test case begins with a single line containing an even integer _w_ ( 2 ≤ _w_ ≤ 1000), the width of the tunnel, and an integer _N_ ( 0 ≤ _N_ ≤ 100), the number of obstacles. The next _N_ lines each contain the description of a single obstacle. The _i_-th obstacle is a simple polygon, specified on a single line containing an integer _n_ $ _{i} $ ( 3 ≤ _n_ $ _{i} $ ≤ 10), the number of vertices, followed by _n_ $ _{i} $ pairs of integers, _x_ $ _{ij} $ and _y_ $ _{ij} $ ( 0 ≤ _x_ $ _{ij} $ ≤ 1000 and -_w_/2 ≤ _y_ $ _{ij} $ ≤ _w_/2 for _j_ = 1,..., _n $ _{i} $_ ), specifying the coordinates of the vertices in counterclockwise order. Note that obstacles in the input may touch or even overlap. However, you are guaranteed that R2D2's initial location will not touch or overlap any obstacle. The vertices of each polygon are unique, no two nonconsecutive edges of the polygon intersect (even at their endpoints), and each polygon is guaranteed to have nonzero area. The end-of-input is denoted by an invalid test case with _w_ = _N_ = 0 and should not be processed.

For each input test case, you must determine the maximum radius _r_ > 0 that R2D2 could have and still be able to plan a path from his starting location (0, 0) to the tunnel exit without overlapping with any of the obstacles. You should print either this maximum radius _r_ (rounded to two decimal places) or the message "impossible" if no such radius exists.