Буи Иссык-Куля
Иссык-Куль — одно из крупнейших высокогорных озёр мира: его длина около 180 км, ширина — до 60 км. Летом в Чолпон-Ате проходит парусная регата, и спасатели огораживают акваторию гонки буями.
Зоной гонки считается наименьший выпуклый многоугольник, содержащий все поставленные буи (выпуклая оболочка). Если буёв пока меньше трёх или все они стоят на одной прямой, зона вырождается в точку или отрезок.
Дежурный спасатель Айдана ведёт журнал из q записей трёх видов:
+ x y— на воду поставлен новый буй в точке(x, y);? x y— нужно определить, находится ли лодка в точке(x, y)внутри зоны гонки или на её границе (ответYESилиNO);A— нужно вывести удвоенную площадь зоны гонки (это всегда целое число).
Буи не убирают, поэтому зона со временем только расширяется. В одной точке может стоять несколько буёв.
Входные данные
В первой строке — целое число q (1 ≤ q ≤ 200 000).
В каждой из следующих q строк — одна запись в описанном формате. Координаты — целые числа, по модулю не превосходящие 10⁹. Первая запись — всегда постановка буя.
Выходные данные
Для каждой записи вида ? и A выведите ответ в отдельной строке.
Пример 1
Вход:
11
+ 0 0
? 0 0
+ 4 0
? 2 0
? 2 1
A
+ 2 4
? 2 1
A
+ 2 -2
A
Выход:
YES
YES
NO
0
YES
16
24
Пояснение
Пока стоят буи (0, 0) и (4, 0), зона — отрезок: точка (2, 0) на нём лежит, а (2, 1) — нет, площадь равна 0. После третьего буя зона — треугольник площади 8, после четвёртого — четырёхугольник площади 12.
Система оценивания
| Подзадача | Баллы | Дополнительные ограничения |
|---|---|---|
| 1 | 20 | q ≤ 2000 |
| 2 | 25 | все буи поставлены раньше первого вопроса |
| 3 | 55 | без дополнительных ограничений |
Баллы за подзадачу начисляются, только если пройдены все её тесты.
Примечание
Удвоенная площадь может достигать 8 · 10¹⁸: она помещается в 64-битный знаковый тип, но промежуточные вычисления могут из него выйти.
Комментарии