eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Tunb Airline

Tunb Airline

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Tunb airline has several flight plans in the Persian Gulf in which there are several beautiful islands. Each flight path looks like a polygonal path on a 2D map starting at one island and ending at another island as depicted in the figure. Recently, the airline has decided to determine how much safe its flights are. For a flight plan, one of the safety measures to be determined is to find out the maximum of dangerousness(p) over all points p on the flight path where dangerousness (p) is the minimum Euclidean distance of p to islands located in the Persian Gulf. If this measure is low, the chance of surviving is high if an incident happens. Your job is to compute this safety measure for a given flight plan.

Входные данные

There are multiple test cases in the input. Each test case starts with a line containing two non-negative integers n and m (0n, m20), where n is the number of islands in the Persian Gulf and m is the number of vertices of the flight path. Then it is followed by m lines each containing two coordinates of the path vertices from first to last. Finally each test case is terminated with the description of islands which are disjoint polygons. For each polygon, first the number of vertices, t, appears in a line (t is at least 3 and at most 30). In the next t lines, the coordinates of the vertices of the polygon is given in either clockwise or counter-clockwise order; each line containing two integers. All coordinates are within range -10000 and 10000. The input finishes with a line containing "0 0" (omit the quotes) which should not be processed as a test case.

Выходные данные

For each test case, output the safety measure defined above rounded to exactly three digits after the decimal point.

Пример

Входные данные #1
1 2
-9 -6
5 1
3
0 16
-16 -12
17 -6
2 3
12 4
16 17
3 9
4
1 0
4 19
19 14
6 12
3
10 10
5 3
18 2
0 0
Выходные данные #1
0.000
2.943
Источник 11th Iran Internet Programming Contest, 28 November, 2013 (7 Azar, 1392)