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

Бассейн реки

Бассейн реки

\includegraphics{https://static.e-olymp.com/content/65/6520e6f5fe08860c80999bb22d24bd801ee92c60.jpg} Задано карту річок деякого континенту. Кожну річку показано як ламану лінію, яка починається у витоці річки і завершується або у точці, де річка впадає в іншу, або гирлом річки. Вершини ламаної - або точки повороту річки, або точки впадення притоків. Будемо розглядати басейн ріки як опуклий многокутник мінімальної площі, який містить річку і всі її притоки. \textit{Примітка}: Згідно цьому визначенню басейну ріки одна і та ж територія може належати басейнам різних рік. Приклад: Показано континент з трьома ріками. Координати річок і площі басейну задано у таблиці. Потрібно знайти максимальну площу басейну річки, розміщену на заданому континенті. \InputFile Перший рядок містить число річок \textbf{N}. У наступних рядках файлу міститься \textbf{N} блоків, які описують річки. Кожен блок номер \textbf{i} складається: \begin{itemize} \item з одного рядка з \textbf{k_i} - числом вершин ламаної, які описують річку; \item \textbf{k_i} рядків, які містять пари дійсних чисел \textbf{x_j} і \textbf{y_j} (\textbf{1} ≤ \textbf{j} ≤ \textbf{k_i}), відокремлених пропуском, - координати точок, які описують річку. \end{itemize} \textbf{1} ≤ \textbf{N} ≤ \textbf{10}, сума \textbf{k_i} ≤ \textbf{1000}, \textbf{-1000} ≤ \textbf{x_j}, \textbf{y_j} ≤ \textbf{1000}. \OutputFile Вивести одне число - площу найбільшого басейну річки з двома знаками після коми.
Ліміт часу 3 секунди
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
3
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
Вихідні дані #1
16.00