← 返回题目列表

Codeforces · 154/E

E. 火星殖民地

中文机器翻译题面 查看原题

第一艘载有地球定居者的飞船登陆火星。殖民者设法在星球表面建造了n个必要的建筑物(可以将其视为一个平面,而建筑物可以视为其上的点)。但有一天,扫描仪记录到了殖民地郊区的可疑活动。决定使用防护力场产生系统来保护殖民地免受可能出现的麻烦。

该系统的工作原理如下:表面包含多个场生成器(它们也可以被视为点)。每个发电机的活动范围是以发电机位置为中心、半径为 r 的圆(圆的边界也包括在该范围内)。系统激活后,它仅将保护力场延伸到所有发电机活动区域内的表面部分。也就是说,受保护的部分是发电机有效范围的交点。

殖民者可用的发电机数量不受限制,但野外发电系统会消耗大量能源。更准确地说,能耗并不取决于发电机的数量,而是与受磁场保护的面积成正比。此外,所有现有建筑物都必须位于保护区内。

确定包含所有建筑物的表面受保护部分的最小可能面积。

输入

第一行包含两个整数 n 和 r (1 ≤ n ≤ 105, 1 ≤ r ≤ 50000) — 相应的建筑物数量和发电机的有效范围。

接下来的 n 行包含建筑物的坐标。第 i + 1 (1 ≤ i ≤ n) 行包含两个小数点后最多三位的实数 xi 和 yi (|xi|, |yi| ≤ 50000) — 第 i 个建筑物的坐标。保证没有两座建筑物位于同一点,并且没有两座不同的建筑物距离小于 1。

保证存在一个半径为 r 的包含所有建筑物的圆。

输出

打印单个实数——包含所有建筑物的受保护部分的最小面积。如果绝对误差或相对误差不超过 10 - 4,则接受答案。

示例

输入 #1

3 5
0.00 0.000
0.0 8.00
6 8.00

输出 #1

78.5398163397

输入 #2

4 1000
0.0 0.0
0 2.00
2.00 2
2.0 0.00

输出 #2

4.0026666140

输入 #3

4 5
3.00 0.0
-3 0.00
0.000 1
0.0 -1.00

输出 #3

8.1750554397

注意

在第一个示例中,给定半径等于给定点外接圆的半径。这就是为什么与之对应的圆就是所寻找的区域。答案是25π。

在第二个示例中,面积几乎与顶点位于给定点的正方形重合。

第三个样本的区域如下图所示。