Выпуклая оболочка
Задано множество точек на плоскости, а также N операций, которые модифицируют это множество. Каждая операция может быть одного из двух следующих типов:
Добавить в множество точку с целыми координатами. При этом абсцисса (т.е. X-координата) новой точки строго больше чем абсциссы всех других точек, которые уже находятся в множестве.
Удалить из множества точку с наибольшей абсциссой.
Напишите программу, которая по заданной последовательности из N операций промоделирует их выполнение и после каждой из них выведет удвоенную площадь выпуклой оболочки точек множества. Перед выполнением первой операции множество точек пустое. Будем считать, что площадь выпуклой оболочки пустого множества точек равна нулю.
Выпуклой оболочкой множества точек на плоскости называется выпуклый многоугольник наименьшей площади, который содержит все точки из множества. Мноугольник называется выпуклым, если отрезок, который соединяет любые две его точки целиком принадлежит этому многоугольнику. Тут под многоугольником понимается граница фигуры вместе с ее внутренностью.
Input
Первая строка содержит одно целое число N (1 ≤ N ≤ 100000) - количество операций, которое требуется выполнить. Последующие N строк содержат по три целых числа – информацию об операциях в зашифрованном формате. Для того, чтобы получить параметры операции с номером i, требуется считать три целых числа T*, X* и Y* (0 ≤ T* ≤ 1, 0 ≤ X*, Y* ≤ 2000000000) с (i + 1)-ой строки, после чего получить число T по следующей формуле: T = (T* + S) mod 2, где S - это удвоенная площадь выпуклой оболочки точек множества до выполнения операции с номером i. Можно убедиться, что S всегда есть целым числом.
Если T = 0, то очередная операция первого типа и координаты (X, Y) новой точки получаются по следующим формулам: X = L + ((S + X*) mod 2 000 000 001), Y = ((Y* + S) mod 2 000 000 001) – 1 000 000 000. Тут L - это максимальная из абсцисс всех точек из множества. Если множество пустое, то L = -1 000 000 000.
Если T = 1, то требуется K раз выполнить операцию второго типа. Число K находится по формуле: K = ((X* + Y* + S) mod Q) + 1. Тут Q - это количество точек в множестве.
Гарантируется, что при правильной расшифровке всех операций выполняются следующие ограничения:
Координаты всех точек, которые добавляются к множеству, не превышают 1 000 000 000 по модулю.
При добавлении новой точки ее абсцисса строго больше чем абсциссы всех точек, которые уже лежат в множестве.
Операция удаления применяется только к непустому множеству точек.
Output
Вывести следует N строк. В строке с номером i требуется вывести удвоенную площадь выпуклой оболочки множества точек, которая образовалась после выполнения первых i операций. Если множество точек оказалось пустым, то площадь его выпуклой оболочки считать равной 0.
Объяснение. После расшифровки тест выглядит таким образом:
T = 0, X = 0, Y = 0
T = 0, X = 1000000, Y = 1000000
T = 0, X = 2000000, Y = -1000000
T = 0, X = 3000000, Y = 0
T = 1, K = 1
T = 1, K = 2