题目252：凸状孔
本帖最后由 欧拉计划 于 2017-1-7 23:10 编辑Convex Holes
Given a set of points on a plane, we define a convex hole to be a convex polygon having as vertices any of the given points and not containing any of the given points in its interior (in addition to the vertices, other given points may lie on the perimeter of the polygon).
As an example, the image below shows a set of twenty points and a few such convex holes. The convex hole shown as a red heptagon has an area equal to 1049694.5 square units, which is the highest possible area for a convex hole on the given set of points.
For our example, we used the first 20 points (T2k−1, T2k), for k = 1,2,…,20, produced with the pseudo-random number generator:
S0 = 290797
Sn+1 = Sn2 mod 50515093
Tn = ( Sn mod 2000 ) − 1000
i.e. (527, 144), (−488, 732), (−454, −947), …
What is the maximum area for a convex hole on the set containing the first 500 points in the pseudo-random sequence?
Specify your answer including one digit after the decimal point.
题目：
给定平面上点的集合，定义凸状孔为内部不含有任何给定点的凸多边形（除了顶点，其它给定点也可以在多边形的边界上）
例如，下图显示了二十个点的集合与一些凸形孔。红色的凸形孔，即红色的七边形。其面积为 1049694.5 单位面积，这是给定点集的凸形孔的最大面积。
在我们的例子中，我们用到 (T2k−1, T2k) 的前 20 个点,，其中 k = 1,2,…,20。这些点由伪随机数生成器产生：
S0 = 290797
Sn+1 = Sn2 mod 50515093
Tn = ( Sn mod 2000 ) − 1000
例如，(527, 144), (−488, 732), (−454, −947), …
给定以上伪随机数序列的前 500 个点，求相应的凸形孔的最大面积。
你的答案要保留小数点后一位。
页:
[1]