시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 498 | 105 | 92 | 28.840% |
원자력 발전소는 현대 문명의 축복이자 저주이다. 원자력 발전소는 많은 위험성이 있지만, 전기를 만드는 가장 싼 방법이다. 이 문제에서는 거리가 멀지 않은 두 원자력 발전소에 어떤 상황에 대해서 생각해 본다.
그림 1. 두 원자력 발전소. (81, 49)와 (77, 33)에 있는 집은 매우 위험한 지역이다.
먼저, 땅이 모두 평평하고, 2차원 좌표 평면 위에 모든 집이 있다고 가정한다. 두 원자력 발전소가 각각 (ax, ay)와 (bx, by)에 있다고 가정한다. 발전소 (ax, ay)와 거리가 R1이내인 곳(R1인 곳도 포함)은 방사능 고위험 지역이다. 발전소 (bx, by)와 거리가 R2이내인 곳(R2인 곳도 포함)도 방사능 고위험 지역이다. 따라서, 원자력 발전소 1과 2의 관계자는 특별한 보호 장비를 방사능 고위험 지역에 있는 집에게 나누어 준다. 따라서, 두 원자력 발전소의 위험 지역에 모두 포함되는 집은 보호 장비를 두 개 받게 된다. 하지만, 이 보호 장비는 하나만 있어도 집을 안전하게 보호할 수 있다.
방사능 고위험 지역의 밖에 있는 집은 방사능 저위험 지역이다. 하지만, 저위험 지역에 있는 집은 보호 장비를 받지 못한다. 이 경우에 보호 장비를 두 개 가지고 있는 집에서 하나를 저위험 지역에 있는 집에게 주면, 저위험 지역도 보호 장비를 하나 가질 수 있다. 이렇게 보호 장비를 나누어주어도, 받지 못하는 집이 있을 수 있다.
집의 위치와 두 원자력 발전소의 위치, 그리고 가능한 R1, R2가 주어졌을 때, 각각의 경우에 대해서, 보호 장비를 가질 수 없는 집의 수를 구하는 프로그램을 작성하시오.
입력은 최대 3개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 아래와 같이 이루어져 있다.
첫째 줄에는 집의 수 N이 주어진다. (0 < N ≤ 200000) 다음 N개 줄에는 집의 좌표 xi, yi가 주어진다. (0 ≤ xi, yi ≤ 20000) 두 집이 같은 곳에 있는 경우는 없다.
다음 줄에는 ax, ay, bx, by, q가 주어진다. (0 ≤ ax, ay, bx, by ≤ 20000, 0 < q ≤ 20000) ax, ay, bx, by는 원자력 발전소의 좌표이고, q는 가능한 R1, R2값의 수이다.
다음 q개 줄에는 R1, R2가 주어진다. (0 < R1, R2 ≤ 13000)
마지막 줄에는 0이 하나 주어진다.
각 테스트 케이스는 q+1 줄을 출력해야 한다. 첫째 줄은 테스트 케이스 번호를 출력한다. 그 다음, 가능한 R1, R2값에 대해서, 보호 장비를 받을 수 없는 집의 수를 출력한다.
11 95 75 27 6 93 5 124 13 34 49 65 61 81 49 77 33 110 50 91 22 110 25 57 42 97 36 2 31 25 25 25 0
Case 1: 2 2
ICPC > Regionals > Asia Pacific > Thailand > 2012 ACM-ICPC Asia Hatyai Regional Programming Contest D번