Problem 252

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 (T_2k−1, T_2k), for k = 1,2,…,20, produced with the pseudo-random number generator:

$S\_0=290797$ $S\_{n+1}=S\_n^2 \text{ mod } 50515093$ $T\_n=\text{(}S\_n \text{ mod } 2000 \text{)}-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.

凸洞

给定平面上一个点集，以这个点集中的点为顶点、且不包含点集中的点在内部（可以在边界上）的凸多边形，称为这个点集的凸洞。

例如，下图展示了20个点组成的点集，以及一系列点集的凸洞。下图中的红色七边形凸洞的面积为1049694.5平方单位，是点集中最大的凸洞。

在这个例子中，我们使用的20个点(T_2k−1, T_2k)是由如下的伪随机数生成器取k = 1,2,…,20生成的：

$S\_0=290797$ $S\_{n+1}=S\_n^2 \text{ mod } 50515093$ $T\_n=\text{(}S\_n \text{ mod } 2000 \text{)}-1000$

也就是 (527, 144), (−488, 732), (−454, −947), …

取这个伪随机序列的前500个点构成的集合，凸洞的最大面积是多少？
注意将你的答案保留小数点后一位小数。