매미나방
시간 제한1초메모리 제한128 MB
고정된 카메라에서 본 나무들의 방향과 고정된 시야각이 주어질 때, 나무를 가장 많이 포함하는 0.1도 단위 각도를 찾는다. 시야 경계 위의 나무는 포함하지 않는다.
문제
공원의 매미나방 발생 상황을 조사하던 관리인과 공원장이 있다. 근처 산 정상에는 원격 조종 카메라가 설치되어 있고, 매미나방이 발생한 나무는 모두 지도 위의 점으로 표시되어 있다.
산의 기온이 내려가고 있어 카메라는 곧 얼어붙어 더 이상 회전할 수 없게 된다. 게다가 이 카메라는 시야각이 좁아, 제한된 각도 범위 안에 들어오는 나무만 보여 줄 수 있다. 카메라가 얼어붙기 전에, 관리인은 가능한 한 많은 발생 나무가 보이도록 카메라를 한 방향으로 고정하려고 한다.
카메라의 위치는 고정되어 있다. 거리는 가시성에 영향을 주지 않는다. 즉, 어떤 나무가 카메라의 시야 각도 범위 안에 들어오는 방향에 있기만 하면 그 나무는 보이는 것으로 본다.
입력
입력은 하나 이상의 데이터 집합으로 이루어진다.
각 데이터 집합의 첫 줄에는 발생 나무의 개수인 음이 아닌 정수 이 주어진다. 이 적힌 줄은 입력의 끝을 의미하며, 처리하지 않는다.
인 데이터 집합에서는 다음이 이어진다.
- 다음 줄에는 실수 세 개가 주어진다: 카메라의 좌표, 좌표, 그리고 카메라의 시야각 (도 단위 각도).
- 이어지는 개의 줄에는 각각 발생 나무 한 그루의 , 좌표가 주어진다. 어떤 나무도 카메라와 같은 좌표에 있지 않다.
모든 좌표는 이상 이하의 실수이다. 시야각 는 이상 이하의 실수이다.
출력
각 데이터 집합에 대해, 각도 범위 안에 들어오는 발생 나무의 수가 최대가 되도록 카메라의 방향 를 정하라.
- 각도는 이 양의 축 방향, 이 양의 축 방향을 가리키도록 측정한다(각도는 시계 방향으로 증가한다).
- 카메라는 도 단위로만 고정되므로, 는 반드시 의 배수여야 한다. 그 사이의 각도는 불가능하다.
- 어떤 나무는 그 방향이 범위의 내부에 엄격히 들어올 때에만 보이는 것으로 센다. 경계선 위에 정확히 놓인 나무는 보이지 않는다.
- 거리는 가시성에 영향을 주지 않는다.
- 최대 개수의 나무를 볼 수 있는 각도가 여러 개라면, 그중 가장 작은 각도를 택하라.
각 데이터 집합마다 다음 형식으로 한 줄을 정확히 출력한다.
Point the camera at angle ### to view ## infested trees.
여기서 ###는 택한 각도 이며 부터 까지의 범위에서 소수점 아래 한 자리까지 출력한다. ##는 보이는 나무의 수로, 정수로 출력한다.
테스트 데이터는 어떤 나무도 경계로부터 도 이내에 있지 않도록 구성되어 있으므로, 경계 부근의 정밀도 문제는 발생하지 않는다.