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

Айсберги

Айсберги

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Таня - морской биолог. Ее цель - измерить влияние изменения климата на популяцию макаронных пингвинов. Как и большинство видов пингвинов, макаронные пингвины обитают в южном полушарии, недалеко от Антарктиды. Таня в первую очередь ориентирована на популяцию макаронных пингвинов возле "Iles Nuageuses" (по-английски "Облачные острова").

Летом лед вокруг островов тает, и острова становятся слишком маленькими, чтобы вместить всех птиц. Некоторые пингвины живут на плавающих вокруг айсбергах. Для своего исследования Тане нужно измерить площадь этих айсбергов.

Используя спутниковые снимки и распознавание изображений, Таня получила карту айсбергов, и Ваша цель - измерить их площадь. Остров, изучаемый Таней, довольно мал, и Землю локально можно представить как плоскую поверхность. Таким образом, карта Тани использует обычную декартову систему координат 2D, а площади вычисляются обычным образом. Например, прямоугольник, параллельный осям, определяемым уравнениями x[1]xx[2] и y[1]yy[2], имеет площадь (x[2] - x[1]) * (y[2] - y[1]).

В представлении Тани айсберг - это многоугольник, представленный его границей. Для каждого айсберга Таня отметила последовательность точек p[1], ..., p[k], определяющих границу айсберга. Различные айсберги никогда не касаются друг друга и никогда не пересекаются. Кроме того, граница айсберга p[1], ..., p[k] всегда является "простым" многоугольником, то есть никакие два отрезка [p[1]; p[2]], ..., [p[k]; p[1]] не пересекаются друг с другом.

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

Первая строка содержит целое число n (1n1000), описывающее количество многоугольников. Затем следуют n блоков строк, каждый из которых описывает многоугольник и состоит из:

  • в первой строке целое число P (3P50) - количество точек, определяющих границу многоугольника,

  • в следующих P строках два целых числа x и y (0x, y10^6) через пробел, координаты каждой граничной точки.

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

Вывести одно целое число: общую площадь, округленную до ближайшего целого числа вниз. Другими словами, следует вывести такое одно целое число I, что общая площадь A многоугольников, описанных во входных данных, находится между I включительно и I + 1 невключительно (IA < I + 1).

Пример

Входные данные #1
1
4
0 0
1 0
1 1
0 1
Выходные данные #1
1
Входные данные #2
2
5
98 35
79 90
21 90
2 36
50 0
3
0 0
20 0
0 20
Выходные данные #2
6100
Источник 2019 ACM Southwestern Europe Regional Contest (SWERC), Париж, Январь 26 (2020), Задача F