기상과의 전쟁

시간 제한1초메모리 제한128 MB

요약
지구 표면의 목표 지점 중에서 지구를 관통하지 않는 가시선을 가진 위성이 하나라도 있는 지점의 수를 센다.
난이도

보통10점 중 5점

유형
기하, 수학, 완전 탐색, 구현
정답자
아직 제출이 없습니다

문제

남쪽 해안이 갑작스러운 허리케인의 공격을 받은 뒤, "영광의 전사"(Glorious Warrior, 이하 GW)는 기상 현상과의 전쟁을 선포했다. 첫 번째 작전은 가능한 한 많은 열대 저기압(tropical depression)을 동시에 선제 타격하는 것이다. GW는 저기압이 폭풍으로 발달하기 전에 무력화하면 다른 저기압의 형성까지 억제할 수 있다고 본다.

GW는 우주 공간의 여러 위치에 배치된 kk기의 위성(우주에서 지표를 공격할 수 있는 킬러 위성)을 보유하고 있고, 지표에는 mm개의 열대 저기압이 존재한다. 각 위성은 자신과 목표 사이에 시야(line of sight)가 확보되어 있기만 하면 목표의 개수에 상관없이 공격할 수 있다. 즉, 위성과 목표를 잇는 선분이 지구를 통과하지 않으면 그 목표를 타격할 수 있다.

적어도 하나의 위성이 타격할 수 있는 서로 다른 목표는 모두 몇 개인가?

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 두 정수 kk와 mm (0<k,m≤1000 < k, m \le 100)이 적힌 줄로 시작한다. 이어서 kk개의 줄에 각각 위성의 위치 x y zx\ y\ z가, 다시 mm개의 줄에 각각 목표(열대 저기압)의 위치 x y zx\ y\ z가 주어진다.

지구는 원점 (0,0,0)(0, 0, 0)을 중심으로 하고 둘레가 40,000 km인 구라고 가정한다. 모든 목표는 지표면 위(10−910^{-9} km 이내)에 있으며, 모든 위성은 지표에서 최소 50 km 이상 떨어진 상공에 있다. 마지막 테스트 케이스 뒤에는 0 0이 적힌 줄이 온다.

출력

각 테스트 케이스마다 타격할 수 있는 목표의 총 개수를 한 줄에 출력한다. 시야가 확보되는 경계로부터 10−810^{-8} km 이내에 놓인 목표는 존재하지 않는다.

예제1

  1. 예제 1

    입력
    3 2
    -10.82404031 -1594.10929753 -6239.77925152
    692.58497298 -5291.64700245 4116.92402298
    3006.49210582 2844.61925179 5274.03201053
    2151.03635167 2255.29684503 5551.13972186
    -1000.08700886 -4770.25497971 4095.48127333
    3 4
    0 0 6466.197723676
    0 6466.197723676 0
    6466.197723676 0 0
    6366.197723676 0 0
    6365.197723676 112.833485488 0
    0 0 6366.197723676
    0 -6366.197723676 0
    0 0
    
    예상 출력
    2
    3