Дана карта рек некоторого континента. Каждая река показана как ломаная линия, которая начинается у истока реки и заканчивается или в точке, где река впадает в другую, или устьем реки. Вершины ломаной - или точки поворота реки, или точки впадения притоков.
Будем рассматривать бассейн реки как выпуклый многоугольник минимальной площади, который содержит реку и все её притоки.
Примечание. Согласно этому определению бассейна реки, одна и та же территория может принадлежать бассейнам различных рек.
Пример. Показан континент с тремя реками. Координаты рек и площади бассейнов даны в таблице.
| Название реки |
x |
y |
Площадь бассейна реки без притоков |
| река 1 |
6 |
9 |
12,5 |
| 5 |
11 |
| 3 |
12 |
| 2 |
10 |
| 1 |
7 |
| |
| река 2 |
7 |
9 |
1,5 |
| 5 |
7 |
| 5 |
5,5 |
| |
| река 3 |
3 |
10 |
9,5 |
| 5 |
8 |
| 4 |
6 |
| 5 |
5,5 |
| 6 |
5 |
| 3 |
5 |
Требуется найти максимальную площадь бассейна реки, расположенной на данном континенте.
Входные данные
Первая строка содержит число рек N. В следующих строках файла содержится N блоков, описывающих реки.
Каждый блок номер i состоит:
из одной строки с k
i - числом вершин ломаной, представляющей реку;
ki строк, содержащих пары вещественных чисел x
j и y
j (1 <= j <= k
i), разделённых пробелом, - координаты точек, описывающих реку.
Ограничения: 1 <= N <= 10, сумма k
i <= 1000, -1000 <= x
j, y
j <= 1000.
Выходные данные
Вывести одно число - площадь наибольшего бассейна реки с двумя знаками после запятой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
6 11
5 13
3 14
1 9
3
7 11
5 9
5 7.5
6
3 12
5 10
4 8
5 7.5
6 7
3 7
|
16.00
|