题目描述

在旭丘幼儿园，有一个为中班小朋友开设的实验室，但是实验室总是有许多杂物，白板前面的票箱就是其中之一。

票箱有一个投票的开口。一天，Mocha 突发奇想，她想看看能不能将白板笔从开口丢进去，可Mocha
尝试了许多次总是被挡住。然而当 Mocha 尝试旋转白板笔时，突然白板笔掉进去了！Mocha 发现当白板笔处于某些角度时就可以丢进票箱，否则就会被挡住。

爱动脑的 Mocha 当然不会放过这个神奇的现象！她将这件事情抽象成了下面的模型：

二维平面上有一个 $n$ 个点的凸多边形，一个位于凸多边形内部或边界上的旋转中心，以及一对平行的直线。Mocha 想请你计算一下，如果她每秒将凸多边形绕旋转中心旋转 $1^{\circ}$，那么在凸多边形旋转一周（即从 $0^{\circ}$ 到 $360^{\circ}$）的过程中，有多长时间凸多边形上所有的点都严格位于两条直线之间（即位于两条直线之间且不在任意一条直线上）呢？

输入格式

第一行有一个整数 $n$ $(3\le n\le 10^5)$，代表凸多边形的点数。

之后 $n$ 行，每行两个整数 $x,y$ $(-10^9\le x,y\le10^9)$，代表凸多边形上第 $i$ 个点的坐标。坐标按照逆时针顺序给出。数据为非严格凸多边形，即可能存在三个及以上的点在同一直线上，但不存在两个坐标相同的点。

第 $n+2$ 行包含两个整数 $x_C,y_C$ $(-10^9\le x_C,y_C\le10^9)$，代表旋转中心。

之后两行，每行四个整数 $x_A,y_A,x_B,y_B$ $(-10^9\le x_A,y_A,x_B,y_B\le10^9)$，表示由 $(x_A,y_A),(x_B,y_B)$ 两点构成的直线，保证两点不同，两条直线平行且不重合。

数据保证旋转中心位于凸多边形内部或边界上且严格位于两条直线之间（即旋转中心可能在凸多边形的顶点上或边上，但旋转中心不会出现在两条平行直线的某一条上)。

输出格式

输出一个实数，表示凸包所有点位于两条直线之间的时间。当且仅当你的答案和正确答案的绝对误差或相对误差不超 $10^{-6}$ 时，你的答案会被视为正确，即假设你的答案为 $a$，正确答案为 $b$，当且仅当 $\frac{\left|a-b\right|}{max{(1,\left|b\right|)}}\le10^{-6}$ 时你的答案会被视为正确答案。

4
0 0
4 0
4 4
0 4
2 2
-1 0 -1 1
5 0 5 1

360.000000000000000

4
0 0
2 0
2 2
0 2
1 1
2 0 2 1
0 0 0 1

0.000000000000000

3
0 0
-3 -2
3 -2
0 -1
1 0 1 -1
-2 0 -2 -1

41.593143321340491

解释 #1

第一个样例初始位置如图所示，其中位于 $(2,2)$ 的点为旋转中心。在整个旋转过程中，凸包上的点始 终位于两条平行直线之间。

第二个样例初始位置如图所示，其中位于 $(1,1)$ 的点为旋转中心。在整个旋转过程中，凸包上的点 或者位于某一条直线上，或者位于两条直线之间的区域外。

第三个样例初始位置如图所示，其中位于 $(0,1)$ 的点为旋转中心。

题目来源

2022-河南省大学生程序设计竞赛 - D题