크레인 운반
시간 제한1초메모리 제한128 MB
고정된 위치와 도달 반경을 가진 크레인들을 이용해 입구에서 시작하여 각 목적지 K개에 장비를 옮길 수 있는지 원판 연결 그래프로 판정하는 문제입니다.
문제
건설 현장은 좌표축과 평행한 직사각형이며, 한 꼭짓점은 (0, 0), 반대쪽 꼭짓점은 (X, Y)이다.
현장 입구는 아래쪽 변의 가운데, 즉 (X/2, 0)에 있다. 현장에는 N대의 크레인이 있고, 각 크레인은 한 점에 고정되어 360도 회전할 수 있으며 최대 작업 반경이 주어진다.
트럭은 입구에 중장비를 내려놓는다. 이후 중장비는 여러 번의 크레인 작업으로 옮겨진다. 한 번의 작업에서 어떤 크레인은 현재 위치의 중장비를 집어 올린 뒤, 그 크레인의 최대 반경 안에 있는 임의의 지점에 내려놓을 수 있다.
K개의 목적지가 주어질 때, 각 목적지까지 중장비를 옮길 수 있는지 판단하라.
입력
첫째 줄에 정수 X와 Y가 주어진다. 2 <= X, Y <= 200이며, X는 짝수이다.
둘째 줄에 크레인의 수 N이 주어진다. 1 <= N <= 50이다.
다음 N개의 줄에는 각 크레인을 나타내는 세 정수 A, B, C가 주어진다. 크레인의 위치는 (A, B)이고 최대 작업 반경은 C이다. 0 <= A <= X, 0 <= B <= Y, 0 <= C <= 200이다.
그다음 줄에 목적지의 수 K가 주어진다. 3 <= K <= 30이다.
다음 K개의 줄에는 목적지 하나를 나타내는 두 정수 D와 E가 주어진다. 목적지의 위치는 (D, E)이고, 0 <= D <= X, 0 <= E <= Y이다.
출력
각 목적지마다 한 줄에 DA 또는 NE를 출력한다. DA는 그 목적지까지 중장비를 옮길 수 있음을, NE는 옮길 수 없음을 의미한다.