ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Четвертьфинал, Рыбинск, 16 октября 2003

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

H. River Basin

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Problem illustration
You are given a map of rivers of some continent. Every river is shown as a broken line, which begins with a river head and ends either at the point where the river flows into another one, or on the river mouth. The vertexes of the broken line are the turning points of the river-bed, or the points of tributary flow.
We will consider the river basin as a convex polygon of minimum area that contains the river and all its tributaries.
Remark. According to the definition of river basin the same territory may belong to the basins of different rivers.
Sample. A continent with three rivers is shown. The coordinates of the rivers and areas of the basins are given in the table.
River nameXYBasin area
river16912
511
312
17
river2791.5
57
55.5
river33109.5
58
46
55.5
65
35
Your task is to calculate the maximum among all river basin areas.

Исходные данные

The first line contains the number of the rivers N. The rest of the input contains N blocks describing the rivers.
Each block i consists of:
  • One line which contains ki – the number of the points in river description;
  • ki lines containing pairs of real numbers xj and yj (1 <= j <= ki), separated by space characters – the coordinates of the points that describe the river-bed.
Limitations.
0 < N <= 10, ∑ki <= 1000, -1000 <= xj, yj <= 1000.
Clarifications.
  • A river basin includes the river with its tributaries, the tributaries of its tributaries, and so on.
  • A river can turn or flow straight at any vertex of the broken line, regardless whether this is a point of tributary flow or not.
  • No two rivers intersect or touch, except when a tributary flows into a river.
  • No two rivers share the same mouth.
  • No two tributaries flow into a river at the same point.
  • Tributaries cannot flow into the river's head or mouth.
  • The points are given with at most 2 digits after the decimal point.

Результат

contains one number – the area of the largest basin calculated with two digit precision.

Примеры

исходные данныерезультат
3
4
6 9
5 11
3 12
1 7
3
7 9
5 7
5 5.5
6
3 10
5 8
4 6
5 5.5
6 5
3 5
16.00
2
4
6 9
5 11
3 12
1 7
6
3 10
5 8
4 6
5 5.5
6 5
3 5
12.00
Автор задачи: © Sergey G. Volchenkov, 2003(volchenkov@yandex.ru); Vladimir N. Pinaev, 2003(vpinaev@mail.ru; http://www.pic200x.chat.ru); Michael Y. Kopachev, 2003 (mkopachev@krista.ru).
Источник задачи: 2003-2004 ACM Central Region of Russia Quarterfinal Programming Contest, Rybinsk, October 15-16, 2003
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1281. River Basin