Informatica Online Judge

  통신 장애 [1212 / 04BC]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 4   Total Tried : 7


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[JOI 2013 Spring Camp]

Background

GSHS는 평면으로 이루어진 나라이다. 이 나라는 n개의 마을이 있으며 각 마을은 1부터 n까지의 번호로 불린다.

마을 i의 좌표는 (i, 0)에 존재하는 점이라고 가정한다.

현재 GSHS에는 각 마을을 연결하는 통신 회선이 존재한다.

통신 장애에 대비해서 통신 회선은 2개의 추가장비셋을 이용하여 이중연결로 강화될 예정이다.

이중으로 추가로 구성될 요소들 추가장비셋1과 추가장비셋2라고 한다.

추가장비셋 k(1 <= k <= 2)에는 허브가 Mk개 존재하고 이들을 연결하는 회선의 수는 n + Mk - 1개가 된다.

추가장비셋 k의 허브는 1부터 Mk까지의 번호를 부여하고, 허브 j는 좌표(Xkj, Ykj)에 존재하는 점이라고 가정한다.

추가장비셋 k의 각 회선은 마을과 허브 또는 허브끼리를 연결하고 있다.

각 회선은 하나의 선분이다.

추가장비셋1의 허브 j의 y좌표 Y1j는 0보다 크다.

추가장비셋2의 허브 j의 y좌표 Y2j는 0보다 작다.

즉, 추가장비셋1의 허브들은 y축으로 양의 방향에 설치되고, 추가장비셋2의 허브들은 y축으로 음의 방향에 설치된다.

어느 2개의 마을을 통신으로 연결하려면, 각각의 마을이 회선으로 연결되어 있어야 한다. 즉, 회선을 따라 이동을 반복하여 한 쪽지점으로부터 다른 쪽지점까지 이동할 수 있다면, 그 2지점은 통신할 수 있다.

추가장비셋1의 회선 혹은 추가장비셋2의 회선 중 어느 한 쪽 회선으로만으로도 연결되면 통신할 수 있다.

다음 그림은 통신회선의 예이다. 회색의 원은 추가장비셋1의 허브들을, 검은 원은 추가장비셋 2의 허브들을 의미하고, 흰색의 원은 마을을 나타낸다.



만약 외부로 부터 공격에 통신망이 얼마나 버틸 수 있을지 궁금해졌다.

외부로부터의 공격은 2개의 정수 a, b(a>=0, b<=0)으로 표현된다.

y좌표가 a보다 큰 모든 허브와 y좌표가 b보다 작은 모든 허브는 파괴된다고 한다.

허브들이 파괴되면 그 허브를 경유하는 통신은 불가능하게 된다.

마을과 각 허브들의 정보가 주어질 때, 또 Q개의 쿼리가 주어진다. 각 쿼리는 공격을 나타낸다.

각 쿼리는 정수 a가 입력으로 들어온다. 이 쿼리에 대해서 모든 마을이 통신하기 위해 필요한 b의 최댓값을 구하는 프로그램을 작성하시오.

Input

첫 번째줄에는 n, M1, M2, Q가 공백으로 구분되어 입력된다.

두 번째줄부터 M1줄에 걸쳐서 추가장비셋1의 허브들의 위치를 나타내는 값 Xi, Yi값이 공백으로 구분되어 입력된다.

다음 줄부터 (N + M1 - 1)줄에 걸쳐서 회선의 정보 t, c, d가 공백으로 구분되어 주어진다.

만약 t 값이 1이라면 마을 c와 허브 d를 연결한다는 의미이고, 2라면 허브 c와 허브 d를 연결한다는 의미이다.

다음 줄부터 M2줄에 걸쳐서 추가장비셋2의 허브들의 위치 Xi, Yi가 공백으로 구분되어 주어진다.

다음 줄부터 (N + M2 - 1)줄에 걸쳐서 회선의 정보 t, c, d가 공백으로 구분되어 입력된다.

t, c, d 등의 각 값의 의미는 추가장비셋1과 2와 같다.

다음 줄부터 Q줄에 걸쳐서 한 줄에 하나의 정수 A_i가 입력된다.

[입력값의 정의역]
1 <= n, M1, M2 <= 100,000
-1,000,000,000 <= X, Y <= 1,000,000,000
1 <= Q <= 100,000
0 <= A <= 1,000,000,000

* 임의의 2개의 회선은 교차하지 않는다. (끝점 이외에는 공유하지 않는다.)


[Sub-Task Info]
#1 : n, M1, M2 <= 1,000 ; Q <= 1,000 (20%)
#2 : 추가제한 사항 없음 (80%)

Output

각 쿼리에 대해서 모든 마을이 통신할 수 있는 b의 최댓값을 출력한다. 만약 답이 0이 될 경우에는 "-0"을 출력하지 않도록 주의한다.

IO Example

입력
4 3 3 1
1 1
3 2
2 3
1 1 1
1 2 1
1 3 2
1 4 2
2 1 3
2 2 3
3 -1
2 -2
1 -3
1 1 3
1 2 2
1 3 1
1 4 1
2 1 2
2 2 3
2


출력
-2

* 이 입력은 왼쪽의 그림에 해당한다.

입력
6 4 5 4
2 1
4 1
3 3
5 2
1 1 1
1 2 1
1 3 2
1 4 2
2 2 4
1 5 4
1 6 4
2 1 3
2 4 3
3 -3
5 -1
2 -2
2 -1
4 -2
1 2 4
1 3 4
1 1 4
2 1 3
1 5 2
1 6 2
1 4 5
2 2 5
1 3 1
2 5 1
3
1
2
0

출력
0
-2
-1
-3

* 이 예는 오른쪽 그림에 해당한다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]