Responsive image

问题 2617 --Mocha上中班啦

2617: Mocha上中班啦

时间限制: 2 Sec  内存限制: 512 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

在旭丘幼儿园,有一个为中班小朋友开设的实验室,但是实验室总是有许多杂物,白板前面的票箱就是其中之一。
票箱有一个投票的开口。一天,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,当且仅当时你的答案会被视为正确答案。

样例输入

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

样例输出

360.000000000000000

提示

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






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

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






来源

[提交][状态]
ACM算法攻关部
  • Anything about this OnlineJudge, Please Contact Administrator. Click add QQ

    OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap

    Copyright 2016 ACM算法攻关部
    关于网站改版