원판으로 볼록 다각형 덮기

고정된 반지름의 원판을 평면 어디에든 놓아 볼록 다각형과 겹치는 넓이를 최대로 만들고, 그 최댓값을 출력한다.

어려움8기하이분 탐색구현아직 제출이 없습니다시간 제한3초메모리 제한512 MB

문제

평평한 종이 위에 볼록 다각형이 하나 그려져 있다. 반지름이 rr인 원판을 종이 위에 올려놓아 다각형과 원판이 겹치는 넓이를 최대로 만들려고 한다. 원판의 중심은 종이 위 어디에나 놓을 수 있고, 중심의 좌표가 정수일 필요는 없다.

다각형과 원판이 겹치는 부분의 넓이가 가장 클 때, 그 넓이를 구하라.

입력

입력은 테스트 케이스 하나로 이루어지고, 형식은 다음과 같다. 입력에 주어지는 값은 모두 정수이다.

n r
x1 y1
.
.
.
xn yn

nn은 다각형의 꼭짓점 개수이고 3n103 \le n \le 10이다. rr은 원판의 반지름이고 1r1001 \le r \le 100이다. xix_iyiy_iii번째 꼭짓점의 좌표이며 0xi1000 \le x_i \le 100, 0yi1000 \le y_i \le 100을 만족한다.

꼭짓점은 반시계 방향으로 주어진다. 다각형은 볼록하다. 즉 모든 꼭짓점의 내각이 180180^\circ보다 작고, 다각형의 경계가 자기 자신과 교차하거나 맞닿는 일은 없다.

출력

다각형과 원판이 겹치는 넓이의 최댓값을 소수점 아래 넷째 자리까지 반올림해 한 줄에 출력한다. 소수점 아래 자릿수는 뒤가 00이더라도 항상 정확히 네 자리여야 한다. 답이 0.50.5이면 0.5000을 출력한다.