Айсберги
Айсберги
Таня - морской биолог. Ее цель - измерить влияние изменения климата на популяцию макаронных пингвинов. Как и большинство видов пингвинов, макаронные пингвины обитают в южном полушарии, недалеко от Антарктиды. Таня в первую очередь ориентирована на популяцию макаронных пингвинов возле "Iles Nuageuses" (по-английски "Облачные острова").
Летом лед вокруг островов тает, и острова становятся слишком маленькими, чтобы вместить всех птиц. Некоторые пингвины живут на плавающих вокруг айсбергах. Для своего исследования Тане нужно измерить площадь этих айсбергов.
Используя спутниковые снимки и распознавание изображений, Таня получила карту айсбергов, и Ваша цель - измерить их площадь. Остров, изучаемый Таней, довольно мал, и Землю локально можно представить как плоскую поверхность. Таким образом, карта Тани использует обычную декартову систему координат 2D, а площади вычисляются обычным образом. Например, прямоугольник, параллельный осям, определяемым уравнениями x1
≤ x ≤ x2
и y1
≤ y ≤ y2
, имеет площадь (x2
- x1
) * (y2
- y1
).
В представлении Тани айсберг - это многоугольник, представленный его границей. Для каждого айсберга Таня отметила последовательность точек p1
, ..., pk
, определяющих границу айсберга. Различные айсберги никогда не касаются друг друга и никогда не пересекаются. Кроме того, граница айсберга p1
, ..., pk
всегда является "простым" многоугольником, то есть никакие два отрезка [p1
; p2
], ..., [pk
; p1
] не пересекаются друг с другом.
Входные данные
Первая строка содержит целое число n (1 ≤ n ≤ 1000), описывающее количество многоугольников. Затем следуют n блоков строк, каждый из которых описывает многоугольник и состоит из:
- в первой строке целое число P (3 ≤ P ≤ 50) - количество точек, определяющих границу многоугольника,
- в следующих P строках два целых числа x и y (0 ≤ x, y ≤
106
) через пробел, координаты каждой граничной точки.
Выходные данные
Вывести одно целое число: общую площадь, округленную до ближайшего целого числа вниз. Другими словами, следует вывести такое одно целое число I, что общая площадь A многоугольников, описанных во входных данных, находится между I включительно и I + 1 невключительно (I ≤ A < I + 1).
1 4 0 0 1 0 1 1 0 1
1
2 5 98 35 79 90 21 90 2 36 50 0 3 0 0 20 0 0 20
6100