eolymp
bolt
Try our new interface for solving problems
Məsələlər

Бассейн реки

Бассейн реки

\includegraphics{https://static.e-olymp.com/content/31/31331e95d2ca92ba727d7ef4ecbc62a784e6cc0c.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 Вывести одно число - площадь наибольшего бассейна реки с двумя знаками после запятой.
Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #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
Çıxış verilənləri #1
16.00