Up Above the World So High
면접 대비시간 제한8초메모리 제한512 MB
원점을 중심으로 하는 별 100개 이하의 위치와 시야 각반경이 주어질 때, 그 반각의 원뿔 안에 들어가는 별의 최대 개수를 구한다.
문제
아이들이 자주 묻는 질문 중 하나는 "하늘에 별이 몇 개나 있나요?"이다. 이상적인 조건이라면 맨눈으로도 북반구에서 약 8천 개의 별을 볼 수 있다. 좋은 망원경이 있으면 훨씬 많은 별을 찾을 수 있지만, 시야가 제한되므로 한 번에 볼 수 있는 별은 오히려 훨씬 적을 수 있다.
아이들은 지구에서 수십억 광년 떨어진 우주선 안에서 부모에게 같은 질문을 할 수도 있다. 그들의 망원경은 우리의 것과 비슷하고 시야가 원형이다. 망원경은 자유롭게 회전할 수 있다. 즉, 시선 벡터는 임의의 값을 가질 수 있다.
별들의 위치와 망원경의 제원이 주어졌을 때, 망원경으로 한 번에 볼 수 있는 별의 최대 개수를 구하시오.
입력
각 테스트 케이스의 첫째 줄에는 별의 개수를 나타내는 양의 정수 N이 주어진다. N은 100을 넘지 않는다. 이어지는 N개의 줄에는 정수 sx, sy, sz가 주어지며, 이는 별의 위치 (sx, sy, sz)를 유클리드 좌표로 나타낸 것이다. -1000 ≤ sx ≤ 1000, -1000 ≤ sy ≤ 1000, -1000 ≤ sz ≤ 1000이고 (sx, sy, sz) ≠ (0, 0, 0)이라고 가정할 수 있다.
그다음 줄에는 망원경 시야의 각반경을 도 단위로 나타내는 양의 정수 ψ (0 < ψ < 90)가 주어진다. 망원경은 좌표계의 원점 (0, 0, 0)에 있다.
각반경 ψ가 0.01도 미만으로 변해도 답에 영향을 주지 않으며, 서로 다른 두 별 P, Q와 원점 O에 대해 ∠POQ가 0.01도보다 크다고 가정할 수 있다.
출력
망원경으로 볼 수 있는 별의 최대 개수를 나타내는 정수를 한 줄에 출력한다. 출력에는 다른 문자도 포함되면 안 된다.
힌트
이 문제 지문은 ACM-ICPC Asia Regional Contest 2006, Yokohama의 "How I Wonder What You Are!"에서 가져왔으며, 작지만 중요한 변경이 있다.