Буи Иссык-Куля


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Иссык-Куль — одно из крупнейших высокогорных озёр мира: его длина около 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-битный знаковый тип, но промежуточные вычисления могут из него выйти.


Комментарии

Еще нет ни одного комментария.