아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

소 떼 울타리 세우기

시간 제한2초메모리 제한256 MB

요약
각 질의는 지금까지 추가된 모든 소가 주어진 직선 위에 놓이지 않고 같은 쪽에 있는지 판정합니다.
난이도

어려움10점 중 8점

유형
기하, 이분 탐색
정답자
아직 제출이 없습니다

문제

농부 John은 소가 멀리 돌아다니지 못하도록 직선 모양의 울타리를 세우려 한다. 후보 위치를 여러 개 골라 두었고, 그중 어느 것을 실제로 쓸 수 있는지 알고 싶어 한다. 울타리는 모든 소가 그 직선의 같은 쪽에 있을 때만 쓸 수 있다. 소가 직선 위에 정확히 놓여 있으면 그 울타리는 쓸 수 없다. 울타리 질의마다 쓸 수 있으면 YES를, 쓸 수 없으면 NO를 답하라.

John은 이따금 새 소를 무리에 들이기도 한다. 새 소가 합류한 순간부터는 그 소까지 나머지 무리와 같은 쪽에 있어야 울타리를 쓸 수 있다.

입력

첫째 줄에 NN (1≤N≤100 0001 \le N \le 100\,000)과 QQ (1≤Q≤100 0001 \le Q \le 100\,000)가 공백으로 구분되어 주어진다. 각각 처음에 무리에 있는 소의 수와 연산의 수다.

다음 NN개 줄에는 소 한 마리의 위치를 나타내는 정수 xx와 yy가 공백으로 구분되어 주어진다.

이어지는 QQ개 줄에는 연산이 하나씩 주어진다. 1 x y는 위치 (x,y)(x, y)에 새 소가 무리에 합류했다는 뜻이다. 2 A B C는 직선 Ax+By=CAx + By = C를 따라 세운 울타리를 쓸 수 있는지 묻는다.

입력 전체에서 소의 위치는 모두 서로 다르며, −109≤x,y≤109-10^9 \le x, y \le 10^9을 만족한다. 울타리 질의는 −109≤A,B≤109-10^9 \le A, B \le 10^9과 −1018≤C≤1018-10^{18} \le C \le 10^{18}을 만족한다. AA와 BB가 동시에 0인 질의는 없다.

출력

울타리 질의마다 쓸 수 있으면 YES를, 그렇지 않으면 NO를 한 줄에 출력한다.

힌트

소 한 마리가 직선 위에 놓이기만 해도 그 울타리는 탈락한다. 나머지 소가 모두 한쪽에 있어도 마찬가지다.

입력과 출력의 양이 많다. 입력은 빠른 방법으로 읽고, 출력은 한 줄마다 flush하지 않는다.

예제2

  1. 예제 1

    입력
    3 4
0 0
0 1
1 0
2 2 2 3
1 1 1
2 2 2 3
2 0 1 1
    예상 출력
    YES
NO
NO

  2. 예제 2

    입력
    1 5
0 0
2 1 0 0
2 1 0 5
2 1 0 -5
1 3 4
2 1 1 3
    예상 출력
    NO
YES
YES
NO