반짝반짝 작은 별, 너는 무엇일까!

면접 대비

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

요약
모든 망원경이 원점에 있을 때, 각 별이 적어도 하나의 망원경 시야각 안에 들어오는지 확인해 관측 가능한 별의 개수를 구합니다.
난이도

쉬움10점 중 3점

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

문제

아이들이 흔히 던지는 질문 중 하나는 "하늘에 별이 몇 개나 있을까?" 입니다. 조건이 좋으면 북반구에서는 맨눈으로도 거의 8,000개에 가까운 별을 볼 수 있습니다. 성능이 좋은 망원경을 쓰면 훨씬 더 많은 별을 찾을 수 있지만, 시야가 좁기 때문에 한 번에 보이는 별은 오히려 적습니다.

지구에서 수십억 광년 떨어진 어느 항성계의 행성에서도 아이들은 부모에게 똑같은 질문을 합니다. 그들의 망원경도 우리의 것과 비슷하게 원형 시야를 가지지만, 그 외계 아이들은 눈이 여러 개여서 여러 망원경으로 서로 다른 방향을 동시에 바라볼 수 있습니다.

별들의 위치, 망원경들, 그리고 각 망원경이 향하는 방향이 주어질 때, 이 망원경들을 통해 볼 수 있는 별이 모두 몇 개인지 세는 것이 당신의 과제입니다.

입력

입력은 하나 이상의 데이터셋으로 이루어지며, 데이터셋의 개수는 5050개 미만입니다.

각 데이터셋의 첫 줄에는 별의 개수를 나타내는 양의 정수 nn (1≤n≤5001 \le n \le 500)이 주어집니다. 이어지는 nn개의 줄에는 각각 세 실수 sxs_x, sys_y, szs_z가 주어지며, 이는 유클리드 좌표에서 별의 위치 (sx,sy,sz)(s_x, s_y, s_z)를 나타냅니다. −1000≤sx≤1000-1000 \le s_x \le 1000, −1000≤sy≤1000-1000 \le s_y \le 1000, −1000≤sz≤1000-1000 \le s_z \le 1000이고 (sx,sy,sz)≠(0,0,0)(s_x, s_y, s_z) \neq (0, 0, 0)임이 보장됩니다.

그다음 줄에는 망원경의 개수를 나타내는 양의 정수 mm (1≤m≤501 \le m \le 50)이 주어집니다. 이어지는 mm개의 줄에는 각각 네 실수 txt_x, tyt_y, tzt_z, ψ\psi가 주어지며, 하나의 망원경을 나타냅니다.

모든 망원경은 원점 (0,0,0)(0, 0, 0)에 있습니다(행성의 크기는 무시합니다). 앞의 세 수는 그 망원경의 시야 중심에 보이는 점 (tx,ty,tz)(t_x, t_y, t_z), 즉 망원경이 향하는 방향을 나타냅니다. −1000≤tx≤1000-1000 \le t_x \le 1000, −1000≤ty≤1000-1000 \le t_y \le 1000, −1000≤tz≤1000-1000 \le t_z \le 1000이고 (tx,ty,tz)≠(0,0,0)(t_x, t_y, t_z) \neq (0, 0, 0)임이 보장됩니다. 네 번째 수 ψ\psi (0≤ψ≤π/20 \le \psi \le \pi/2)는 망원경 시야의 각반경(라디안)입니다.

ii번째 별의 방향과 jj번째 망원경의 중심 방향이 이루는 각을 θi,j\theta_{i,j}, jj번째 망원경의 각반경을 ψj\psi_j라 합시다. ii번째 별은 θi,j<ψj\theta_{i,j} < \psi_j일 때, 그리고 오직 그때만 jj번째 망원경을 통해 관측할 수 있습니다. 모든 쌍 ii, jj에 대해 ∣θi,j−ψj∣>0.00000001|\theta_{i,j} - \psi_j| > 0.00000001임이 보장됩니다.

그림 1: 망원경이 향하는 방향과 그 각반경.

입력의 끝은 00 하나만 있는 줄로 표시됩니다.

출력

각 데이터셋마다 한 줄에 정수 하나를 출력합니다. 이는 적어도 하나의 망원경을 통해 관측할 수 있는 별의 개수입니다. 그 밖의 어떤 문자도 출력해서는 안 됩니다. 두 개 이상의 망원경으로 볼 수 있는 별이라도 중복해서 세지 않습니다.

예제3

  1. 예제 1

    입력
    3
    100 0 500
    -500.243 -200.1 -300.5
    0 300 200
    2
    1 1 1 0.65
    -1 0 0 1.57
    3
    1 0 0
    0 1 0
    0 0 1
    4
    1 -1 -1 0.9553
    -1 1 -1 0.9554
    -1 -1 1 0.9553
    -1 1 -1 0.9554
    3
    1 0 0
    0 1 0
    0 0 1
    4
    1 -1 -1 0.9553
    -1 1 -1 0.9553
    -1 -1 1 0.9553
    -1 1 -1 0.9553
    0
    
    예상 출력
    2
    1
    0
    
  2. 예제 2

    입력
    1
    1 0 0
    1
    1 0 0 0.5
    0
    
    예상 출력
    1
    
  3. 예제 3

    입력
    1
    1 0 0
    1
    -1 0 0 0.5
    0
    
    예상 출력
    0