기상과의 전쟁
시간 제한1초메모리 제한128 MB
지구 표면의 목표 지점 중에서 지구를 관통하지 않는 가시선을 가진 위성이 하나라도 있는 지점의 수를 센다.
문제
남쪽 해안이 갑작스러운 허리케인의 공격을 받은 뒤, "영광의 전사"(Glorious Warrior, 이하 GW)는 기상 현상과의 전쟁을 선포했다. 첫 번째 작전은 가능한 한 많은 열대 저기압(tropical depression)을 동시에 선제 타격하는 것이다. GW는 저기압이 폭풍으로 발달하기 전에 무력화하면 다른 저기압의 형성까지 억제할 수 있다고 본다.
GW는 우주 공간의 여러 위치에 배치된 기의 위성(우주에서 지표를 공격할 수 있는 킬러 위성)을 보유하고 있고, 지표에는 개의 열대 저기압이 존재한다. 각 위성은 자신과 목표 사이에 시야(line of sight)가 확보되어 있기만 하면 목표의 개수에 상관없이 공격할 수 있다. 즉, 위성과 목표를 잇는 선분이 지구를 통과하지 않으면 그 목표를 타격할 수 있다.
적어도 하나의 위성이 타격할 수 있는 서로 다른 목표는 모두 몇 개인가?
입력
입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 두 정수 와 ()이 적힌 줄로 시작한다. 이어서 개의 줄에 각각 위성의 위치 가, 다시 개의 줄에 각각 목표(열대 저기압)의 위치 가 주어진다.
지구는 원점 을 중심으로 하고 둘레가 40,000 km인 구라고 가정한다. 모든 목표는 지표면 위( km 이내)에 있으며, 모든 위성은 지표에서 최소 50 km 이상 떨어진 상공에 있다. 마지막 테스트 케이스 뒤에는 0 0이 적힌 줄이 온다.
출력
각 테스트 케이스마다 타격할 수 있는 목표의 총 개수를 한 줄에 출력한다. 시야가 확보되는 경계로부터 km 이내에 놓인 목표는 존재하지 않는다.