Cover the Polygon with Your Disk

Time limit3sMemory limit512 MB

Summary

Place a fixed-radius disk anywhere on the plane to maximize the area shared with a convex polygon, and print that maximum.

Level: Hard8 of 10
Topics: Geometry, Binary search, Implementation
Solved: No attempts yet

Problem

A convex polygon is drawn on a flat sheet of paper. You put a disk of radius $r$ on the paper so that the area shared by the polygon and the disk is as large as possible. The center of the disk can go anywhere on the paper, and its coordinates do not have to be integers.

Compute that largest shared area.

Input

The input is one test case in the following format. Every value in the input is an integer.

n r
x1 y1
.
.
.
xn yn

$n$ is the number of vertices of the polygon, with $3 \le n \le 10$ . $r$ is the radius of the disk, with $1 \le r \le 100$ . $x_i$ and $y_i$ are the coordinates of the $i$ -th vertex, with $0 \le x_i \le 100$ and $0 \le y_i \le 100$ .

The vertices are given in counterclockwise order. The polygon is convex, so every interior angle is smaller than $180^\circ$ and the boundary never crosses or touches itself.

Output

Print the largest shared area on one line, rounded to four digits after the decimal point. Always print exactly four digits after the decimal point, even when they are zeros. For an answer of $0.5$ , print 0.5000.

Examples6

Example 1
Input
```
4 4
0 0
6 0
6 6
0 6
```
Expected output
```
35.7595
```
Example 2
Input
```
3 1
0 0
2 1
1 3
```
Expected output
```
2.1131
```
Example 3
Input
```
3 1
0 0
100 1
99 1
```
Expected output
```
0.0198
```
Example 4
Input
```
4 1
0 0
100 10
100 12
0 1
```
Expected output
```
3.1376
```

Example 5

Input

Expected output

177.7282

Example 6

Input

Expected output

7181.6033