当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

3479:RoBa Has a Second Art Gallery!

Special Judge 特殊评判
题目描述

One year and a half after owning his first art gallery, RoBa has recently built his second art gallery. Just like before, in order to protect his cherished artworks from theft, he has hired security guards. In addition, He wants to install one or two surveillance cameras so that he can watch by himself day and night everything happening inside the gallery.

RoBa is reusing his plan of camera monitoring which has proved working with his first gallery. The gallery has a nice shape of a convex polygon. (Different from that of his first gallery, this polygon may not have cocircular vertices.) Tall and opaque walls stand on the edges of the polygon. A camera can be installed anywhere inside the gallery hanging from the ceiling or on the walls. A single camera’s sight is an infinite wedge emanating from the place the camera is installed and not blocked by any walls. The cameras are fixed. Once installed, they cannot move or rotate themselves.

The cost of having a camera installed is proportional to the angle spanned by the wedge the camera covers. RoBa wants to minimize the cost of his monitoring plan. Given the shape of the gallery, how should the camera(s) be installed?

In the illustration to the left (not describing the sample test case), two cameras should be installed at points A and C covering wedges α and β respectively. The cost can be measured by the sum of ∠CAD and ∠ACB.
输入解释

The input consists of a single test case. The first line contains an integer n (3 ≤ n ≤ 100), indicating that he polygon has n vertices. Each of the next n lines contains a pair of real numbers xi, yi, the coordinates of the i-th vertex. The vertices are listed in counterclockwise order. Any three of them are not collinear.

输出解释

Output the sum of angles spanned by the camera(s) in radians. A special checker program that admits an absolute error of 10−6 is used to verify your answer.

输入样例
4
0 0
1 0
1 1
0 1
输出样例
1.5707963267949

该题目是Virtual Judge题目,来自 北京大学POJ

源链接: POJ-3479

最后修改于 2020-10-29T07:02:35+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
5000 131072