Migrated from Lutece 3284 Wings of Courage

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

TAG：半平面交、旋转卡壳

本题面由 空気力学の詩 友情提供

鸢泽美咲打算给家中的地板铺上地毯，为此她事先购买了两块大小相同的半径均为 $r$ 的圆形地毯。

美咲的房间的平面图呈凸多边形的形状，并通过二维平面上的 $n$ 个顶点坐标来给出。

虽然圆形的地毯并不能总是完全地覆盖地板，不过她仍然希望找到一种最小化未被地毯覆盖的区域面积的摆放方式。

需要注意的是在摆放地毯的过程中两块地毯之间可以重叠，但地毯本身不能被裁剪或折叠（包括沿地板边缘剪裁或折叠）。

Input

输入的第一行包括两个正整数 $n,r$，分别表示房间对应的凸多边形的顶点数，以及两块地毯的半径。

接下来的 $n$ 行每行两个整数 $(x_i,y_i)$，表示房间的第 $i$ 个顶点的坐标，按逆时针顺序给出。

Output

输出一行一个数表示未被地毯覆盖的区域面积的最小值，请采用 printf("%e\n", ans); 或 printf("%Le\n", ans); 输出。

Samples

4 3
0 0
10 0
10 8
0 8

2.764216e+01

4 1
-1 -1
1 -1
1 1
-1 1

8.584073e-01

Constraints

$3\le n\le 10^5$，$1\le r\le 10^7$，$-10^7\le x_i,y_i\le 10^7$

输入数据保证房间的所有顶点按照逆时针顺序给出。所有顶点的坐标不同，且房间相邻的两面墙不共线。保证地毯一定能不折叠的放在美咲的房间中。

Resources

2024 UESTC ICPC Training for Geometry