Mainak and the Bleeding Polygon

题意翻译

### **题目大意** 以逆时针顺序给出笛卡尔平面上 $n (4 \leqslant n \leqslant 5000)$ 个点 $A_1,A_2,...,A_n$ 的坐标，从而确定一凸多边形。该凸多边形的性质有如下保证： - 所有点的坐标均为整数且 $-10^{9} \leqslant x,y \leqslant 10^{9}$ 。 - 对于该凸多边形的任意内角 $\alpha$ ，均有 $90^{\circ} \leqslant \alpha < 180^{\circ}$ 。 现从凸多边形的任意两边上分别取出两点，将所有由两点所确定的、长度不超过 $1$ 的弦所经过的凸多边形内部区域**标红**。求标红区域的面积。 ### **输入格式** 第一行输入 $n$ 。 之后 $n$ 行每行给出 $1$ 个点的坐标。 ### **输出格式** 只输出标红区域的面积，保留 $11$ 位小数。误差不超过 $10^{-4}$ 即视为正确。

题目描述

Mainak has a convex polygon $ \mathcal P $ with $ n $ vertices labelled as $ A_1, A_2, \ldots, A_n $ in a counter-clockwise fashion. The coordinates of the $ i $ -th point $ A_i $ are given by $ (x_i, y_i) $ , where $ x_i $ and $ y_i $ are both integers. Further, it is known that the interior angle at $ A_i $ is either a right angle or a proper obtuse angle. Formally it is known that: - $ 90 ^ \circ \le \angle A_{i - 1}A_{i}A_{i + 1} < 180 ^ \circ $ , $ \forall i \in \{1, 2, \ldots, n\} $ where we conventionally consider $ A_0 = A_n $ and $ A_{n + 1} = A_1 $ . Mainak's friend insisted that all points $ Q $ such that there exists a chord of the polygon $ \mathcal P $ passing through $ Q $ with length not exceeding $ 1 $ , must be coloured $ \color{red}{\text{red}} $ . Mainak wants you to find the area of the coloured region formed by the $ \color{red}{\text{red}} $ points. Formally, determine the area of the region $ \mathcal S = \{Q \in \mathcal{P} $ | $ Q \text{ is coloured } \color{red}{\text{red}}\} $ . Recall that a chord of a polygon is a line segment between two points lying on the boundary (i.e. vertices or points on edges) of the polygon.

输入输出格式

输入格式

The first line contains an integer $ n $ ( $ 4 \le n \le 5000 $ ) — the number of vertices of a polygon $ \mathcal P $ . The $ i $ -th line of the next $ n $ lines contain two integers $ x_i $ and $ y_i $ ( $ -10^9 \le x_i, y_i \le 10^9 $ ) — the coordinates of $ A_i $ . Additional constraint on the input: The vertices form a convex polygon and are listed in counter-clockwise order. It is also guaranteed that all interior angles are in the range $ [90^\circ ; 180^\circ ) $ .

输出格式

Print the area of the region coloured in $ \color{red}{\text{red}} $ . Your answer is considered correct if its absolute or relative error does not exceed $ 10^{-4} $ . Formally, let your answer be $ a $ , and the jury's answer be $ b $ . Your answer is accepted if and only if $ \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

说明

In the first example, the polygon $ \mathcal P $ can be visualised on the Cartesian Plane as: