Mainak 有一个凸多边形 $$$\mathcal P$$$,其 $$$n$$$ 顶点以逆时针方式标记为 $$$A_1、A_2、\ldots、A_n$$$。第 $$$i$$$ 点 $$$A_i$$$ 的坐标由 $$$(x_i, y_i)$$$ 给出,其中 $$$x_i$$$ 和 $$$y_i$$$ 都是整数。
此外,已知$$$A_i$$$处的内角是直角或适当的钝角。正式可知:
- $$$90 ^ \circ \le \angle A_{i - 1}A_{i}A_{i + 1} < 180 ^ \circ$$$, $$$\forall i \in \{1, 2, \ldots, n\}$$$,其中我们通常认为 $$$A_0 = A_n$$$ 和 $$$A_{n + 1} = A_1$$$。
Mainak 的朋友坚持认为所有点 $$$Q$$$ 存在穿过 $$$Q$$$ 且长度不超过 $$$1$$$ 的多边形 $$$\mathcal P$$$ 的弦,必须着色为 $$$\color{red}{\text{red}}$$$。
Mainak 希望您找到由 $$$\color{red}{\text{red}}$$$ 点形成的彩色区域的面积。
正式地,确定区域 $$$\mathcal S = \{Q \in \mathcal{P}$$$ | 的面积$$$Q \text{ 是彩色的 } \color{red}{\text{red}}\}$$$。
回想一下,多边形的弦是位于多边形边界上的两点(即顶点或边上的点)之间的线段。
输入
第一行包含一个整数 $$$n$$$ ($$$4 \le n \le 5000$$$) — 多边形 $$$\mathcal P$$$ 的顶点数。
接下来的 $$$n$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — $$$A_i$$$ 的坐标。
对输入的附加约束:顶点形成凸多边形并按逆时针顺序列出。还保证所有内角都在 $$$[90^\circ 范围内; 180^\约)$$$。
输出
打印 $$$\color{red}{\text{red}}$$$ 中着色的区域的面积。
如果您的答案的绝对或相对误差不超过 $$$10^{-4}$$$,则视为正确。
正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。当且仅当 $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}$$$ 时,您的答案才会被接受。
示例
输入 #1
4 4 5 4 1 7 1 7 5
输出 #1
1.17809724510
输入 #2
5 -3 3 3 1 4 2 -1 9 -2 9
输出 #2
1.07823651333
注意
在第一个示例中,多边形 $$$\mathcal P$$$ 可以在笛卡尔平面上可视化为: