2041 : 통신 방해
- 제한시간
- 2000 ms
- 메모리제한
- 256 MB
- 해결횟수
- 0 회
- 시도횟수
- 0 회
문제
정올국은 평면 상에 존재하는 나라이다. 이 나라에는 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 의 최댓값을 구하는 프로그램을 작성하시오.
입력형식
출력형식
입력 예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 |