위성
시간 제한4초메모리 제한512 MB
반원 행성 위에 위성이 추가·삭제될 때, 두 위성의 커버 영역이 행성 밖에서 겹치면서 다른 살아 있는 위성의 커버 영역에 들어가지 않는 지점이 있는지 판정한다.
문제
Real Cosmic Communications(RCC)는 우주의 맨 끝에 있는 머나먼 행성에서 가장 큰 통신 회사이다. RCC는 통신 위성을 발사한다.
이 행성은 우주의 맨 끝에 있으므로 모양이 반원이다. 반지름은 r이고, 지름의 양 끝은 점 A와 B이다. 직선 AB는 우주의 경계이므로, 한쪽 반평면에는 행성도, RCC 위성도, 그 밖의 어떤 것도 없다. 좌표계는 다음과 같이 정한다. 원점은 선분 AB의 중점이고, OX축은 직선 AB와 일치하며, 행성은 전부 y > 0인 반평면에 있다.
위성은 행성 위의 점을 제외한 우주의 임의의 점에 있을 수 있다. 위성은 우주의 경계 너머에도, 경계 위에도 있지 않다. 즉, 좌표 y > 0을 만족한다. 위성 안테나는 위성을 꼭짓점으로 하고 두 변이 점 A와 B를 향하는 각을 덮도록 향한다. 이 영역을 위성의 커버리지 영역이라고 부른다.
아래 그림은 좌표계와 한 위성의 커버리지 영역을 나타낸다.
RCC가 세워졌을 때 행성 주위에는 위성이 없었다. 그 뒤로 다음 유형 중 하나에 해당하는 사건이 여러 번 일어났다.
- 1 x y: 새 위성을 발사해 점 (x, y)에 둔다. 위성은 움직이지 않고 발사된 점에 그대로 있다. 발사 순서대로 i번째 위성에 번호 i를 붙인다.
- 2 i: i번 위성을 제거한다.
- 3 i j: 위성 i와 j 사이에 통신 채널을 만들려고 시도한다. 통신 채널을 만들려면 중계기가 필요하다. 중계기는 행성 내부에 있으면 안 되지만, 행성의 반원 경계 위나 그 위쪽에 있을 수는 있다. 중계기는 위성 i와 j의 커버리지 영역 안에 있어야 한다. 신호 간섭을 피하기 위해 다른 어떤 위성의 커버리지 영역에도 있으면 안 된다. 물론 중계기는 우주 안에 있어야 하므로 좌표 y > 0을 만족한다.
각각의 통신 채널 생성 시도마다 가능한지 여부를 판별해야 한다.
예제 테스트의 위성 위치는 다음과 같다.
입력
첫째 줄에 정수 r과 n이 주어진다. r은 행성의 반지름이고 n은 사건의 수이다 (1 ≤ r ≤ 10^9, 1 ≤ n ≤ 5·10^5).
다음 n개 줄에 주어진 형식대로 사건이 주어진다.
위성 좌표는 정수이며 |x| ≤ 10^9, 0 < y ≤ 10^9를 만족한다. 동시에 존재하는 두 위성이 같은 점을 차지할 수 없다. 각 위성과 행성 중심 사이의 거리는 r보다 엄격히 크다.
유형 2와 3의 사건은 그 순간에 존재하는 위성만 가리킨다. 모든 유형 3 사건에서 i ≠ j이다.
출력
각 유형 3 사건마다 통신 채널을 만들 수 있으면 «YES»를, 만들 수 없으면 «NO»를 한 줄에 하나씩 출력한다.