문제
정올이는 새로 만들어지는 신도시에 편의점을 오픈하려 계획하고 있다.
신도시는 아래 그림과 같은 모습으로 도로를 건설할 예정이다.
그림에서 원으로 표시된 부분은 편의점이 들어설 수 있는 후보지인 상가들의 위치이고, 선은 도로를 나타내며 선 옆에 표시된 값은 도로의 길이다.
이 지역에는 대규모 아파트 단지가 세 군데 있는데, 각 아파트의 위치는 그림에서 A, B, C로 표시된 원이다.
이 지역의 모든 교차로는 연결된 도로의 개수가 5개 이하이고, 도로를 통해 어떤 장소라도 찾아갈 수 있다.
위 그림에서 8번 위치의 상가에 편의점을 개설한다고 하자.
8번 위치의 상가에서 아파트 단지 A, B, C까지의 최단 경로 길이는 각각 3, 3 ,4이다.
이 값들은 2번 위치의 상가에서 아파트 단지 A, B, C까지 최단 경로의 길이인 2, 2, 3보다 각각 더 크다.
사람들은 더 가까운 매장을 이용하는 경향이 있기 때문에, 아파트 단지까지의 거리를 비교할 때 8번 위치의 상가는 각 아파트까지의 거리에서 2번 위치보다 불리한 위치이다.
10번 위치의 상가의 경우는 아파트 단지 A, B, C까지의 거리가 각각 4, 1, 5이므로, 2번 위치의 상가와 비교하면 아파트 단지 B에는 유리하고 아파트 단지 A와 C에는 불리하다.
이런 이유 때문에 정올이는 다음의 기준에 맞춰 위치를 선정하려고 한다.
p번 상가에서 아파트 단지 A, B, C까지의 최단 경로 길이를 각각 a, b, c라고 하고 다른 q번 상가가 존재해서 q번 상가에서 아파트 단지 A, B, C까지의 최단 경로 길이를 각각 x, y, z라고 할 때, a > x 이고 b > y 이고 c > z이면 p번 상가에는 매장을 설치하지 않는다.
질의로서 편의점 후보지가 하나 주어질 때 그 곳에 매장을 차릴 수 있는지 여부를 판별하는 프로그램을 작성하시오.
질의는 여러 개가 들어올 수 있으며, 아파트 단지가 위치한 장소에도 매장을 설치할 수 있다.
입력
첫 번째 줄에는 상가의 개수를 나타내는 정수
둘째 줄에는 아파트 단지의 위치를 나타내는 세 개의 정수
세 번째 줄에는 도로의 개수를 나타내는 정수
그 다음
그 다음 줄에는 질의의 개수를 나타내는 정수
그 다음
[제약 조건]
1≤N≤100,000 상가들은
1 부터N 까지의 번호로 구분된다.A, B, C 는 모두 다른 값이며 상가의 위치 중의 하나로 주어진다.1≤Z≤10,000 입력에서 같은 도로가 중복해서 들어오는 경우는 없다.
1≤T≤10,000 1≤Q≤N
출력
각 질의
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 30점 | |
| #2 | 33점 | |
| #3 | 37점 | 추가 제약 조건 없음 |
예제
10
4 5 7
13
1 2 1
2 3 1
2 4 2
2 5 2
3 6 2
3 7 2
2 8 1
1 9 1
1 10 1
5 1 2
6 5 2
10 5 1
10 6 1
10
1
2
3
4
5
6
7
8
9
10
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
문제에 설명에 나오는 예제이다.
로그인해야 코드를 작성할 수 있어요.