Informatica Online Judge

  비밀 요원 [2161 / 0871]

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


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

[koistudy.net(33rd 신승원)]

Background

경기과학고가 세워진 터에는 어떤 역사가 숨어 있을까? 시간을 거슬러 올라가 보자.

2000년 전, 경기과학고가 있던 자리에는 도시국가 "인호국"의 성이 세워져 있었다. 인호국의 성은 1에서 N까지 번호가 붙은 N개의 망루가 M개의 성벽들로 연결되어 있는 튼튼한 구조로, 성벽은 두 망루를 잇는 선분 형태로, 망루 외의 지점에서 교차하지 않으며, 모든 망루 사이를 성벽 위를 타고 이동할 수 있도록 되어 있었다. 인호국의 왕 인호는 그 성 안에 국가의 기밀 정보를 숨겨 놓았다.

인호국은 또 다른 도시국가 "민석국"과 경쟁 중에 있었는데, 민석국의 왕 민석이는 인호국의 기밀 정보를 캐내기 위해 비밀 요원들을 성 안으로 보내기로 한다. 비밀 요원들은 매우 빠르기 때문에 성벽이 가로막고 있지 않는 한 이동 시간을 무시할 수 있다. 또, 비밀 요원들은 인호국의 성벽을 타고 넘어다닐 수 있는데, 이 때는 성벽의 높이만큼의 시간이 걸린다.

민석이는 비밀 요원들에게 총 Q개의 지점을 순서대로 방문해 조사하고 오라는 명령을 내렸다. 이 지점들은 성벽이나 망루와 겹치지 않음이 보장된다. 민석이는 비밀 요원들이 똑똑하다고 생각했기 때문에, 방문해야 하는 지점들만 알려 주면 알아서 빠르게 갔다 올 것이라고 믿고 있다.

하지만, 비밀 요원들은 생각만큼 똑똑하지 않았다. 그들은 어떻게 움직여야 가장 빠를지 전혀 감을 못 잡고 있다. 비밀 요원들이 빠르게 움직이지 못하면 들켜버리고 말 것이다. 비밀 요원들을 도와주자!

Input

첫 번째 줄에는 망루의 개수 N (1≤N≤200000) 과 성벽의 개수 M (N−1≤M≤N+100) 이 주어진다.

다음 N개의 줄에는 순서대로 i번 망루가 놓인 좌표 xi, yi가 주어진다. (|xi|,|yi|≤109)

다음 M개의 줄에는 각 성벽이 잇는 두 망루의 번호 ui, vi와 망루의 높이 hi가 주어진다. (1≤ui,vi≤N, 1≤hi≤109)

성벽은 망루 외의 지점에서 교차하지 않음이 보장되며, 임의의 두 망루 사이를 성벽을 타고 오갈 수 있음이 보장된다.

그 다음 줄에는 민석이가 내린 명령의 개수 Q (1≤Q≤200000) 가 주어진다.

다음 Q개의 줄에는 각 지점의 좌표 ai, bi가 주어진다. (|ai|,|bi|≤109)

모든 지점은 성벽이나 망루와 겹치지 않음이 보장된다.

Output

Q줄에 걸쳐, i번째 줄에는 i−1번째 지점에서 i번째 지점으로 가는 최단 시간을 출력한다.

(단, 0번째 지점의 좌표는 (∞, ∞)로 가정한다)

IO Example

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

출력
4
2
3

* 설명 : 그림으로 설명하면 다음과 같다.



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