색깔 사각형과 쿼리

시간 제한3초메모리 제한512 MB

요약
서로 교차하거나 접하지 않는 축에 평행한 사각형 네 변에 색이 칠해져 있을 때, 두 점을 잇는 평면 경로가 반드시 지나야 하는 색 종류의 최솟값을 쿼리마다 구한다.
난이도

어려움10점 중 9점

유형
그래프, DFS, 기하, 구현
정답자
아직 제출이 없습니다

문제

색깔 사각형은 내부가 비어 있고 동서남북을 이루는 선분 44개가 각각 11, 22, 33, 44, 55, 66의 색 중 하나로 칠해져 있는 직사각형이다. 사각형의 꼭짓점은 연결된 두 선분의 색 중 더 큰 값을 가지는 색으로 칠한다.

준혁이는 색깔 사각형 NN개를 서로 다른 두 사각형의 어떤 선분이 교차하지도, 접하지도 않도록 평면 위에 배치해 놓았다. 또, 사각형의 선분이 xx축 또는 yy축과 평행하도록 배치하였다.

다음 쿼리 QQ개를 수행하자.

  • 두 점 (x_s,y_s),(x_e,y_e)(x\_s, y\_s), (x\_e,y\_e)가 주어질 때, (x_s,y_s)(x\_s, y\_s)에서 시작하여 (x_e,y_e)(x\_e,y\_e)에 도착하는 임의의 경로가 사각형의 선분의 색 중 최소 몇 가지 종류의 색을 지나야 하는지 출력한다. 두 점 사이를 이동하는 경로는 평면 위의 모든 공간을 자유롭게 이동할 수 있다.

입력

첫째 줄에 사각형의 개수 NN이 주어진다. (1≤N≤200,000)(1 \leq N \leq 200\\,000)

다음 NN개의 줄에 준혁이가 배치한 사각형의 정보를 나타내는 정수 x_1x\_1, y_1y\_1, x_2x\_2, y_2y\_2, c_1c\_1, c_2c\_2, c_3c\_3, c_4c\_4이 공백으로 구분되어 주어진다.

  • 입력되는 사각형의 왼쪽 아래 점은 (x_1,y_1)(x\_1, y\_1), 오른쪽 위의 점은(x_2,y_2)(x\_2, y\_2)이다. (−109≤x_1\<x_2≤109;(-10^9 \leq x\_1\<x\_2 \leq 10^9; −109≤y_1\<y_2≤109)-10^9 \leq y\_1\<y\_2 \leq 10^9)
  • c_1c\_1, c_2c\_2, c_3c\_3, c_4c\_4는 각각 사각형의 왼쪽 선분, 위쪽 선분, 오른쪽 선분, 아래쪽 선분의 색을 나타낸다. (1≤c_i≤6)(1 \leq c\_i \leq 6)

다음 줄에 쿼리의 개수 QQ가 입력된다. (1≤Q≤200,000)(1 \leq Q \leq 200\\,000)

다음 QQ개의 줄에 쿼리 x_sx\_s, y_sy\_s, x_ex\_e, y_ey\_e가 입력된다. 점 (x_s,y_s)(x\_s,y\_s)와 (x_e,y_e)(x\_e, y\_e)은 준혁이가 배치한 사각형의 선분 위에 있지 않다. (−109≤x_s,x_e,y_s,y_e≤109)(-10^9 \leq x\_s,x\_e,y\_s,y\_e \leq 10^9)

출력

QQ개의 줄에 걸쳐 각 쿼리의 답을 한 줄에 하나씩 출력한다.

예제2

  1. 예제 1

    입력
    2
1 1 5 5 1 2 3 4
2 2 4 4 2 3 4 1
1
3 3 6 3
    예상 출력
    1

  2. 예제 2

    입력
    4
1 1 10 10 1 2 3 4
2 11 4 13 2 1 2 1
4 4 5 5 6 6 6 6
6 6 8 9 5 5 4 4
4
2 5 6 5
7 7 3 12
15 -1 9 9
-1 -1 5 -1
    예상 출력
    0
2
1
0