← 返回题目列表

Codeforces · 1510/F

F. 纤维形状

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

想象一块板上有 $$$n$$$ 引脚,第 $$$i$$$ 引脚位于 $$$(x_i, y_i)$$$。为简单起见,我们将问题限制为销钉放置在凸多边形顶点的情况。

然后,取一根长度为 $$$l$$$ 的不可拉伸的绳子,并将其放在所有引脚周围。将一支铅笔放在绳子内,并在销钉周围画一条曲线,尝试向各个可能的方向拉动绳子。下图显示了将一根绳子绑在别针上并用铅笔拉动的示例(一个点 $$$P$$$)。

您的任务是找到该曲线内的区域。形式上,对于给定的凸多边形 $$$S$$$ 和长度 $$$l$$$ 让我们定义一个 纤维形状 $$$F(S, l)$$$ 作为点集 $$$t$$$,使得 $$$S \cup \{t\}$$$ 的凸包周长不超过 $$$l$$$。求 $$$F(S, l)$$$ 的面积。

输入

第一行包含两个整数 $$$n$$$ 和 $$$l$$$ ($$$3 \le n \le 10^4$$$; $$$1 \le l \le 8 \cdot 10^5$$$) — 多边形 $$$S$$$ 的顶点数和字符串长度。接下来的 $$$n$$$ 行包含整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$-10^5 \le x_i, y_i \le 10^5$$$) - 逆时针顺序的多边形顶点坐标。多边形的所有内角都严格小于$$$\pi$$$。长度 $$$l$$$ 超过多边形的周长至少 $$$10^{-3}$$$。

输出

输出一个浮点数——纤维形状 $$$F(S, l)$$$ 的面积。如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。

示例

输入
复制

3 4
0 0
1 0
0 1

输出
复制

3.012712585980357

输入
复制

4 5
0 0
1 0
1 1
0 1

输出
复制

5.682061989789656

输入
复制

5 17
0 0
2 -1
3 0
4 3
-1 4

输出
复制

37.719371276930820

注意

下图说明了示例测试。