문제
정올국은 평면 상에 존재하는 나라이다. 이 나라에는 N 개의 도시가 있으며 각 도시는 1 부터 N 까지의 번호로 불린다.
도시 i의 좌표는 (i, 0)에 존재하는 점이라고 가정한다.
현재 정올국에는 각 도시를 연결하는 통신 회선이 존재한다.
통신 장애에 대비해서 통신 회선은 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 의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 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 <= Q <= 100,000
-1,000,000,000 <= Xi, Yi <= 1,000,000,000
0 <= Ai <= 1,000,000,000
임의의 2 개의 회선은 교차하지 않는다. (끝점 이외에는 공유하지 않는다.)
< 제약 사항 > 입력 데이터의 20% 는 n, M1, M2 <= 1,000 , Q <= 1,000 이다. 입력 데이터의 80% 는 추가 제약이 없다.
출력
각 쿼리에 대해서 모든 도시가 통신할 수 있는 b의 최댓값을 출력한다. 만약 답이 0이 될 경우에는 "-0"을 출력하지 않도록 주의한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 20점 | |
| #2 | 80점 | 추가 제한 없음 |
예제1
4331
11
32
23
111
121
132
142
213
223
3-1
2-2
1-3
113
122
131
141
212
223
2
-2
예제2
6454
21
41
33
52
111
121
132
142
224
154
164
213
243
3-3
5-1
2-2
2-1
4-2
124
134
114
213
152
162
145
225
131
251
3
1
2
0
0
-2
-1
-3