아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

매미나방

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

요약
고정된 카메라에서 본 나무들의 방향과 고정된 시야각이 주어질 때, 나무를 가장 많이 포함하는 0.1도 단위 각도를 찾는다. 시야 경계 위의 나무는 포함하지 않는다.
난이도

보통10점 중 6점

유형
투 포인터, 정렬, 기하, 수학
정답자
아직 제출이 없습니다

문제

공원의 매미나방 발생 상황을 조사하던 관리인과 공원장이 있다. 근처 산 정상에는 원격 조종 카메라가 설치되어 있고, 매미나방이 발생한 나무는 모두 지도 위의 점으로 표시되어 있다.

산의 기온이 내려가고 있어 카메라는 곧 얼어붙어 더 이상 회전할 수 없게 된다. 게다가 이 카메라는 시야각이 좁아, 제한된 각도 범위 안에 들어오는 나무만 보여 줄 수 있다. 카메라가 얼어붙기 전에, 관리인은 가능한 한 많은 발생 나무가 보이도록 카메라를 한 방향으로 고정하려고 한다.

카메라의 위치는 고정되어 있다. 거리는 가시성에 영향을 주지 않는다. 즉, 어떤 나무가 카메라의 시야 각도 범위 안에 들어오는 방향에 있기만 하면 그 나무는 보이는 것으로 본다.

입력

입력은 하나 이상의 데이터 집합으로 이루어진다.

각 데이터 집합의 첫 줄에는 발생 나무의 개수인 음이 아닌 정수 NN이 주어진다. 00이 적힌 줄은 입력의 끝을 의미하며, 처리하지 않는다.

N≥1N \ge 1인 데이터 집합에서는 다음이 이어진다.

  • 다음 줄에는 실수 세 개가 주어진다: 카메라의 XX 좌표, YY 좌표, 그리고 카메라의 시야각 VV(도 단위 각도).
  • 이어지는 NN개의 줄에는 각각 발생 나무 한 그루의 XX, YY 좌표가 주어진다. 어떤 나무도 카메라와 같은 좌표에 있지 않다.

모든 좌표는 −500.0-500.0 이상 500.0500.0 이하의 실수이다. 시야각 VV는 0.10.1 이상 179.9179.9 이하의 실수이다.

출력

각 데이터 집합에 대해, 각도 범위 A±V/2A \pm V/2 안에 들어오는 발생 나무의 수가 최대가 되도록 카메라의 방향 AA를 정하라.

  • 각도는 0.00.0이 양의 YY축 방향, 90.090.0이 양의 XX축 방향을 가리키도록 측정한다(각도는 시계 방향으로 증가한다).
  • 카메라는 0.10.1도 단위로만 고정되므로, AA는 반드시 0.10.1의 배수여야 한다. 그 사이의 각도는 불가능하다.
  • 어떤 나무는 그 방향이 A±V/2A \pm V/2 범위의 내부에 엄격히 들어올 때에만 보이는 것으로 센다. 경계선 위에 정확히 놓인 나무는 보이지 않는다.
  • 거리는 가시성에 영향을 주지 않는다.
  • 최대 개수의 나무를 볼 수 있는 각도가 여러 개라면, 그중 가장 작은 각도를 택하라.

각 데이터 집합마다 다음 형식으로 한 줄을 정확히 출력한다.

Point the camera at angle ### to view ## infested trees.

여기서 ###는 택한 각도 AA이며 0.00.0부터 359.9359.9까지의 범위에서 소수점 아래 한 자리까지 출력한다. ##는 보이는 나무의 수로, 정수로 출력한다.

테스트 데이터는 어떤 나무도 경계로부터 0.010.01도 이내에 있지 않도록 구성되어 있으므로, 경계 부근의 정밀도 문제는 발생하지 않는다.

예제2

  1. 예제 1

    입력
    5
    25.0 25.0 45.0
    25.5 35.0
    35.0 30.0
    45.0 45.0
    40.0 48.5
    20.0 18.0
    0
    
    예상 출력
    Point the camera at angle 22.6 to view 3 infested trees.
    
  2. 예제 2

    입력
    1
    0.0 0.0 90.0
    0.0 100.0
    1
    0.0 0.0 30.0
    100.0 0.0
    2
    0.0 0.0 60.0
    0.0 -100.0
    -100.0 0.0
    0
    
    예상 출력
    Point the camera at angle 0.0 to view 1 infested trees.
    Point the camera at angle 75.1 to view 1 infested trees.
    Point the camera at angle 150.1 to view 1 infested trees.