원판으로 볼록 다각형 덮기
시간 제한3초메모리 제한512 MB
고정된 반지름의 원판을 평면 어디에든 놓아 볼록 다각형과 겹치는 넓이를 최대로 만들고, 그 최댓값을 출력한다.
문제
평평한 종이 위에 볼록 다각형이 하나 그려져 있다. 반지름이 인 원판을 종이 위에 올려놓아 다각형과 원판이 겹치는 넓이를 최대로 만들려고 한다. 원판의 중심은 종이 위 어디에나 놓을 수 있고, 중심의 좌표가 정수일 필요는 없다.
다각형과 원판이 겹치는 부분의 넓이가 가장 클 때, 그 넓이를 구하라.
입력
입력은 테스트 케이스 하나로 이루어지고, 형식은 다음과 같다. 입력에 주어지는 값은 모두 정수이다.
n r
x1 y1
.
.
.
xn yn
은 다각형의 꼭짓점 개수이고 이다. 은 원판의 반지름이고 이다. 와 는 번째 꼭짓점의 좌표이며 , 을 만족한다.
꼭짓점은 반시계 방향으로 주어진다. 다각형은 볼록하다. 즉 모든 꼭짓점의 내각이 보다 작고, 다각형의 경계가 자기 자신과 교차하거나 맞닿는 일은 없다.
출력
다각형과 원판이 겹치는 넓이의 최댓값을 소수점 아래 넷째 자리까지 반올림해 한 줄에 출력한다. 소수점 아래 자릿수는 뒤가 이더라도 항상 정확히 네 자리여야 한다. 답이 이면 0.5000을 출력한다.