만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

땅

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

요약
계수가 -1, 0, 1인 직선이 차례로 추가되고, 각 질의마다 두 점이 지금까지의 직선으로 나뉜 같은 영역에 있는지 판별합니다.
난이도

어려움10점 중 8점

유형
분할 정복, 유니온 파인드, 기하
정답자
아직 제출이 없습니다

문제

Farmer Lasagna는 꿈에 그리던 땅을 샀다. 이 땅에서 그의 소들이 지내고, 그는 옥수수를 기른다. 소는 옥수수를 좋아해서 닿을 수 있는 작물은 모두 먹어 치운다. 그래서 Lasagna는 소가 넘을 수 없을 만큼 높고 튼튼한 긴 벽을 세우려 한다. Lasagna는 스웨덴 공연 준비로 바빠서 땅을 정리하는 일을 도와 달라고 너에게 부탁했다.

땅은 좌표평면이고, 각 벽은 그 평면 위의 직선이다. Lasagna는 Q개의 질의를 보내며, 질의는 다음 두 종류 중 하나다.

  1. 방정식 ax+by=cax + by = c로 주어진 벽을 세운다. 이 식을 만족하는 모든 점 (x,y)(x, y)가 이루는 직선이다. Lasagna는 aa와 bb가 -1부터 1까지의 정수임을 보장한다.

  2. 지금까지 세워진 벽을 기준으로, 소가 점 (x1,y1)(x_1, y_1)에 있고 옥수수 작물이 점 (x2,y2)(x_2, y_2)에 심겨 있다. 소가 (x2,y2)(x_2, y_2)에 도달해서 작물을 망가뜨릴 수 있는가?

모든 질의에 답하도록 도와줄 수 있는가?

입력

첫 줄에 질의의 개수 QQ (1≤Q≤3000001 \le Q \le 300000)가 주어진다.

이어지는 QQ개의 줄은 다음 두 형식 중 하나다.

  1. "1 a b c". aa, bb, cc는 정수이고, −1≤a,b≤1-1 \le a, b \le 1, a≠0a \ne 0 또는 b≠0b \ne 0, −3⋅108≤c≤3⋅108-3 \cdot 10^8 \le c \le 3 \cdot 10^8이다. 테스트 데이터에서는 벽을 세우는 시점에 기존 벽 중에 새 벽과 모든 점이 겹치는 벽이 없음을 보장한다.

  2. "2 x1 y1 x2 y2". x1x_1, y1y_1, x2x_2, y2y_2는 정수이고, −108≤x1,y1,x2,y2≤108-10^8 \le x_1, y_1, x_2, y_2 \le 10^8이다. (x1,y1)(x_1, y_1)은 소의 위치이고, (x2,y2)(x_2, y_2)는 옥수수 작물의 위치다. 테스트 데이터에서는 그 시점에 두 점 모두 어떤 벽 위에도 놓이지 않으며, 두 점은 서로 다름을 보장한다.

출력

두 번째 형식의 각 질의마다, 소가 작물에 닿을 수 있으면 "DA", 그렇지 않으면 "NE"를 한 줄에 하나씩 출력한다.

힌트

첫 번째 예제에서 첫 번째 직선은 x축이며, y좌표가 양수인 점과 음수인 점을 나눈다. 두 번째 직선은 y축이며, 두 직선이 함께 점들을 사분면별로 나눈다.

세 번째 예제의 그림에는 모든 벽에 해당하는 직선과 질의된 모든 점이 나와 있다.

예제3

  1. 예제 1

    입력
    4
1 0 1 0
2 -1 2 2 1
1 -1 0 0
2 -1 2 2 1
    예상 출력
    DA
NE

  2. 예제 2

    입력
    5
1 -1 -1 2
1 1 -1 3
2 0 0 -4 5
2 5 -3 3 1
2 1 -5 -10 2
    예상 출력
    DA
NE
NE

  3. 예제 3

    입력
    8
2 -2 3 1 2
1 1 -1 -3
2 1 2 -2 3
2 3 3 1 2
1 0 1 1
2 3 3 5 6
1 1 0 4
2 1 2 5 6
    예상 출력
    DA
NE
DA
DA
NE