퍼레이드
시간 제한2초메모리 제한256 MB
볼록 다각형과 내부의 한 점, 그리고 k개의 고정된 방향이 주어질 때, 전체 계를 회전시켜 각 방향으로 중심에서 다각형 경계까지의 거리 합을 최소로 만드는 문제다.
문제
아주 먼 나라에서는 다른 아주 먼 나라와의 전쟁 승전 기념일마다 퍼레이드가 열린다. 정부는 퍼레이드를 최대한 화려하게 만들려고 하지만 비용은 많이 들이지 않으려 한다.
퍼레이드는 해마다 볼록 각형 모양의 광장에서 열린다. 오랜 경험에 따르면 화려함을 높이려면 광장을 개의 구역으로 나누어야 하는데, 그 방법은 다음과 같다. 광장의 중심으로 삼을 점을 하나 정하고, 그 점에서 광장의 가장자리까지 여러 개의 가랜드를 이어 붙인다. 이웃한 가랜드 사이의 각도는 정해진 값과 정확히 같아야 한다(쌍마다 값이 다를 수 있다). 정부는 비용을 아끼기 위해 모든 가랜드의 길이 합을 최소로 만들고 싶어 한다. 가랜드 전체를 광장의 중심을 기준으로 어떤 각도만큼 회전하는 것만이 길이 합에 영향을 줄 수 있다. 모든 가랜드의 길이 합으로 가능한 최솟값을 구하라.
그림 왼쪽은 예제를 입력에 주어진 그대로 나타낸 것이고, 오른쪽은 최적으로 회전시킨 뒤의 모습이다.
입력
첫째 줄에는 광장의 모양인 다각형의 꼭짓점 개수 이 정수로 주어진다. () 다음 개의 줄에는 다각형 꼭짓점의 좌표가 주어진다. 꼭짓점은 반시계 방향 순서로 주어진다. 모든 좌표는 정수이고 절댓값이 10000을 넘지 않는다. 주어진 다각형은 퇴화하지 않은 볼록 다각형이다. 어떤 세 꼭짓점도 한 직선 위에 있지 않다.
그다음 줄에는 광장 중심의 좌표가 주어진다. 이 좌표도 정수이고, 중심은 광장 내부에 엄격히 들어 있음이 보장된다.
그다음 줄에는 정수 가 주어진다. () 이는 이어 붙일 가랜드의 개수다. 마지막 줄에는 가랜드가 놓일 수 있는 위치 하나가 주어진다. 각 가랜드가 축의 양의 방향을 기준으로 반시계 방향으로 얼마나 회전되어 있는지를 도 단위로 나타낸 각도가 하나씩 주어진다. 모든 각도는 0에서 359까지의 정수 도이다.
출력
가랜드 전체를 어떤 각도만큼 회전시킨 뒤의 최소 길이 합을 실수 하나로 출력한다. 답의 오차는 이하여야 한다.
가랜드 전체는 임의의 각도만큼 회전시킬 수 있으며, 그 각도가 정수 도일 필요는 없다.