← 返回题目列表

Codeforces · 1726/H

H. 迈纳克和出血多边形

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

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$$$ 可以在笛卡尔平面上可视化为: