Финальный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"E" Спутники
Ограничение по времени 4 секунды
Ограничение по памяти 256 мегабайт

Real Cosmic Communications — самая крупная телекоммуникационная компания на далёкой планете на самом краю Вселенной. Основное направление деятельности RCC — запуск спутников связи.

Поскольку планета находится на краю Вселенной, она имеет форму полукруга. Его радиус равен r, концы диаметра — A и B. Прямая AB — это край Вселенной, поэтому в нижней полуплоскости нет ни планеты, ни спутников компании RCC, ни чего бы то ни было ещё. Введём систему координат следующим образом: начало отсчёта — в середине отрезка AB, ось OX совпадает с прямой AB, планета лежит в полуплоскости y > 0.

Спутник связи может находиться в любой точке Вселенной, кроме точек планеты. Спутник не находится за краем вселенной или на ее границе, то есть имеет координату y > 0. Антенны спутника направлены таким образом, что для связи ему доступен угол с вершиной в спутнике и сторонами, которые проходят через точки A и B. Будем называть эту область зоной покрытия спутника. Границы этой области тоже принадлежат зоне покрытия.

На рисунке показана система координат и зона покрытия одного спутника.

В момент основания RCC около планеты не было ни одного их спутника. С тех пор происходили события следующих типов:

  1. 1 x y — запустить новый спутник и поместить его в точку с координатами (x, y). Спутники компании RCC никуда не двигаются и остаются на месте, пока их не уберут. Спутник, запущенный i-м, получает номер i, нумерация с единицы.
  2. 2 i — убрать спутник номер i.
  3. 3 i j — попытаться установить связь между спутниками i и j. Для этого необходимо установить ретранслятор. Он не может располагаться внутри планеты, но может быть на поверхности или висеть над ней. Ретранслятор должен находиться в зоне покрытия спутников i и j. Кроме того, чтобы не создавать помех, он не должен находиться в зоне покрытия никакого другого спутника. Разумеется, ретранслятор должен находиться внутри вселенной, то есть иметь координату y > 0.

Для каждой попытки установить связь требуется определить, возможно ли это сделать.

В примере входных данных расположение спутников следующее:

Формат входных данных

В первой строке входных данных заданы целые числа r и n — радиус планеты и количество событий (1 ≤ r ≤ 109, 1 ≤ n ≤ 5·105).

В следующих n строках заданы события в приведённом выше формате.

Координаты спутников целые и удовлетворяют ограничениям |x| ≤ 109, 0 < y ≤ 109. Два спутника не могут одновременно находиться в одной точке. Расстояние от спутника до центра планеты строго больше r.

Гарантируется, что в событиях типа 2 и 3 спутники, которые в них задействованы, на момент события существуют. В событиях типа 3 выполнено i ≠ j.

Формат выходных данных

Для каждого события типа 3 выведите в отдельной строке «YES», если возможно установить связь, и «NO» в противном случае.

Примеры
Входные данные
5 8
1 -5 8
1 -4 8
1 -3 8
1 2 7
3 1 3
2 2
3 1 3
3 3 4
Выходные данные
NO
YES
YES
 

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.