在旭丘幼儿园,有一个为中班小朋友开设的实验室,但是实验室总是有许多杂物,白板前面的票箱就是其中之一。
票箱有一个投票的开口。一天,Mocha 突发奇想,她想看看能不能将白板笔从开口丢进去,可 Mocha尝试了许多次总是被挡住。然而当 Mocha 尝试旋转白板笔时,突然白板笔掉进去了!Mocha 发现当白板笔处于某些角度时就可以丢进票箱,否则就会被挡住。
爱动脑的 Mocha 当然不会放过这个神奇的现象!她将这件事情抽象成了下面的模型:
二维平面上有一个 n 个点的凸多边形,一个位于凸多边形内部或边界上的旋转中心,以及一对平行的直线。Mocha 想请你计算一下,如果她每秒将凸多边形绕旋转中心旋转 1◦,那么在凸多边形旋转一周(即从 0◦ 到 360◦)的过程中,有多长时间凸多边形上所有的点都
严格位于两条直线之间(即位于两条直线之间且不在任意一条直线上)呢?
第一行有一个整数 n(3 ≤ n ≤ 105),代表凸多边形的点数。
之后 n 行,每行两个整数 x, y(−109 ≤ x, y ≤ 109),代表凸多边形上第 i 个点的坐标。坐标按照逆时针顺序给出。数据为非严格凸多边形,即可能存在三个及以上的点在同一直线上,但不存在两个坐标相同的点。
第 n + 2 行包含两个整数 xC, yC(−109 ≤ xC, yC ≤ 109),代表旋转中心。
之后两行,每行四个整数 xA, yA, xB, yB(−109 ≤ xA, yA, xB, yB ≤ 109),表示由 (xA, yA),(xB, yB)两点构成的直线,保证两点不同,两条直线平行且不重合。
数据保证旋转中心位于凸多边形
内部或边界上且
严格位于两条直线之间(即旋转中心可能在凸多边形的顶点上或边上,但旋转中心不会出现在两条平行直线的某一条上)。
输出一个实数,表示凸包所有点位于两条直线之间的时间。当且仅当你的答案和正确答案的绝对误差或相对误差不超过 10−6 时,你的答案会被视为正确,即假设你的答案为 a,正确答案为 b,当且仅当
时你的答案会被视为正确答案。
第一个样例初始位置如图所示,其中位于 (2, 2) 的点为旋转中心。在整个旋转过程中,凸包上的点始终位于两条平行直线之间。
第二个样例初始位置如左图所示,其中位于 (1, 1) 的点为旋转中心。在整个旋转过程中,凸包上的点或者位于某一条直线上,或者位于两条直线之间的区域外。
第三个样例初始位置如右图所示,其中位于 (0, −1) 的点为旋转中心。