시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 512 MB | 873 | 190 | 146 | 24.172% |
상수는 진표의 열렬한 팬이다. 그는 팬심을 담아 진표에게 직접 만든 선풍기를 선물해 주었다. 선풍기를 돌리고 놀던 진표는 선풍기를 일정 각도 이상 돌리면 날개의 자취가 원 형태가 된다는 것을 발견했다.
선풍기의 회전 중심을 원점으로 하는 좌표평면 위에 선풍기의 날개를 놓았다고 가정하자. 이때 선풍기의 날개는 원점을 포함하며 꼭짓점이 N개인 단순다각형으로 나타낼 수 있다. 또한 날개는 안전을 위해 다음과 같은 조건을 만족하도록 디자인되었다.
선풍기 날개 내부에 있는 임의의 점 P에 대해, 원점 O와 P를 잇는 선분 위의 모든 점 역시 날개 내부에 있다.
이때, 날개의 자취가 원이 되는 최소 회전 각도를 구해 보자. 선풍기는 반시계 방향으로 돌아간다.
첫 줄에 선풍기 날개의 꼭짓점의 수 N(3 ≤ N ≤ 300,000)이 주어진다.
두 번째 줄부터 N개의 줄에 걸쳐 각 꼭짓점의 좌표가 반시계 방향으로 순서대로 주어진다. 각 좌표는 x 좌표와 y 좌표를 의미하는 두 개의 정수로 이루어지며, 각 좌푯값의 절댓값은 106 이하이다.
이 다각형은 원점을 포함하며, 인접한 두 선분을 제외한 다른 선분끼리는 만나지 않는다. 또한 다각형에서 연속한 3개의 점이 한 직선 위에 있지 않음이 보장된다.
선풍기를 반시계 방향으로 θ만큼 돌렸을 때 날개의 자취가 원이 되는 최소 θ를 도(°) 단위로 구해 출력한다. 절대 또는 상대 오차가 10-6 이하면 정답으로 처리된다.
5 2 2 -2 2 -2 -2 0 -1 2 -2
90.000000
4 2 2 2 3 -2 -2 -2 -3
180.000000
첫 번째 예제의 선풍기는 아래와 같다.
이를 반시계 방향으로 45° 돌렸을 때 자취는 아래와 같다. 처음 도형과 마지막 도형을 짙게 칠하였다.
이렇게 90°를 돌리는 순간 자취는 반지름이 2√2인 원이 된다. 따라서 답은 90이다.
University > 서울대학교 > 2018 서울대학교 프로그래밍 경시대회 > Division 2 D번