만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

원판으로 볼록 다각형 덮기

시간 제한3초메모리 제한512 MB

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

어려움10점 중 8점

유형
기하, 이분 탐색, 구현
정답자
아직 제출이 없습니다

문제

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

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

입력

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

n r
x1 y1
.
.
.
xn yn

nn은 다각형의 꼭짓점 개수이고 3≤n≤103 \le n \le 10이다. rr은 원판의 반지름이고 1≤r≤1001 \le r \le 100이다. xix_i와 yiy_i는 ii번째 꼭짓점의 좌표이며 0≤xi≤1000 \le x_i \le 100, 0≤yi≤1000 \le y_i \le 100을 만족한다.

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

출력

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

예제6

  1. 예제 1

    입력
    4 4
    0 0
    6 0
    6 6
    0 6
    
    예상 출력
    35.7595
    
  2. 예제 2

    입력
    3 1
    0 0
    2 1
    1 3
    
    예상 출력
    2.1131
    
  3. 예제 3

    입력
    3 1
    0 0
    100 1
    99 1
    
    예상 출력
    0.0198
    
  4. 예제 4

    입력
    4 1
    0 0
    100 10
    100 12
    0 1
    
    예상 출력
    3.1376
    
  5. 예제 5

    입력
    10 10
    0 0
    10 0
    20 1
    30 3
    40 6
    50 10
    60 15
    70 21
    80 28
    90 36
    
    예상 출력
    177.7282
    
  6. 예제 6

    입력
    10 49
    50 0
    79 10
    96 32
    96 68
    79 90
    50 100
    21 90
    4 68
    4 32
    21 10
    
    예상 출력
    7181.6033