시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 14 8 7 53.846%

문제

A convex polygon is drawn on a flat paper sheet. You are trying to place a disk in your hands to cover as large area of the polygon as possible. In other words, the intersection area of the polygon and the disk should be maximized.

입력

The input consists of a single test case, formatted as follows. All input items are integers.

n r
x1 y1
.
.
.
xn yn

n is the number of vertices of the polygon (3 ≤ n ≤ 10). r is the radius of the disk (1 ≤ r ≤ 100). xi and yi give the coordinate values of the i-th vertex of the polygon (1 ≤ i ≤ n). Coordinate values satisfy 0 ≤ xi ≤ 100 and 0 ≤ yi ≤ 100.

The vertices are given in counterclockwise order. As stated above, the given polygon is convex. In other words, interior angles at all of its vertices are less than 180°. Note that the border of a convex polygon never crosses or touches itself.

출력

Output the largest possible intersection area of the polygon and the disk. The answer should not have an error greater than 0.0001 (10−4).

예제 입력 1

4 4
0 0
6 0
6 6
0 6

예제 출력 1

35.759506

예제 입력 2

3 1
0 0
2 1
1 3

예제 출력 2

2.113100

예제 입력 3

3 1
0 0
100 1
99 1

예제 출력 3

0.019798

예제 입력 4

4 1
0 0
100 10
100 12
0 1

예제 출력 4

3.137569

예제 입력 5

10 10
0 0
10 0
20 1
30 3
40 6
50 10
60 15
70 21
80 28
90 36

예제 출력 5

177.728187

예제 입력 6

10 49
50 0
79 10
96 32
96 68
79 90
50 100
21 90
4 68
4 32
21 10

예제 출력 6

7181.603297