Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Бассейн реки

(Время: 1 сек. Память: 16 Мб Сложность: 67%)

Дана карта рек некоторого континента. Каждая река показана как ломаная линия, которая начинается у истока реки и заканчивается или в точке, где река впадает в другую, или устьем реки. Вершины ломаной – или точки поворота реки, или точки впадения притоков.

Будем рассматривать бассейн реки как выпуклый многоугольник минимальной площади, который содержит реку и все её притоки. Одна и та же территория может принадлежать бассейнам различных рек.

В качестве примера приведем континент с тремя реками. Координаты рек и площади бассейнов даны в таблице:

 Название реки     x       y     Площадь бассейна реки без притоков  Рисунок
река 1 69 12,5
511
312
210
17
 
река 2 79 1,5
57
55,5
 
река 3 310 9,5
58
46
55,5
65
35

Требуется найти максимальную площадь бассейна реки, расположенной на данном континенте.

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

Первая строка входного файла INPUT.TXT содержит число рек N. В следующих строках файла содержится N блоков, описывающих реки. Каждый блок номер i состоит:

  • из одной строки с ki – числом вершин ломаной, представляющей реку;
  • ki строк, содержащих пары вещественных чисел xj и yj (1 ≤ j ≤ ki), разделённых пробелом, – координаты точек, описывающих реку.

Ограничения: 1 ≤ N ≤ 10, сумма ki ≤ 1000, -1000 ≤ xj, yj ≤ 1000.

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

В выходной файл OUTPUT.TXT выведите одно число – площадь наибольшего бассейна реки с двумя знаками после запятой.

Примеры

INPUT.TXTOUTPUT.TXT
13
5
6 9
5 11
3 12
2 10
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
22
5
6 9
5 11
3 12
2 10
1 7
6
3 10
5 8
4 6
5 5.5
6 5
3 5
12.50

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483