凸洞

给定平面上的一个点集，以这个点集中的一些点为顶点、且内部不包含这个点集中其它点的凸多边形称为这个点集的一个凸洞。

例如，下图展示了由20个点组成的一个点集，以及其中的一些凸洞。图中红色七边形凸洞的面积为1049694.5，是这个点集中最大的凸洞。

上图中点由如下的伪随机数生成器取$k=1,2,\ldots,20$并以$(T_{2k-1},T_{2k})$为坐标，即$(527, 144), (−488, 732), (−454, −947), \ldots$生成的： \begin{align*} S_0&=290797\\ S_{n+1}&=S_n^2 \bmod{50515093} \\ T_n&=(S_n \bmod 2000)-1000 \end{align*} 取这个伪随机序列的前1000项，按同样方式组成含有500个点的集合，则其中最大凸洞的面积是多少？答案保留一位小数。

本题难度:

解答

凸洞的生成似乎和给定顶点的k个最近顶点算法有关，不过本人未找到进一步的资料，且本题数据量不大，因而此处仅使用穷举法。

遍历点集，对每个点P，考虑将坐标系平移到以P为原点时上半平面及x轴正半轴上的点。

将这些点按极角大小排序，并依次考虑排序后相邻两点与P组成的一系列三角形，遍历这些三角形，合并公共边（这样既满足凸性也排除了内部有点的情况），并用动态规划的思想，以$d(i,j)$来记录和更新第i个和第j个点之间能构成的最大凸多边形的面积。

最终结果是$104924.0$。

import math

t=[]
s=290797
for i in range(1000):
    s=(s*s)%50515093
    t.append((s%2000)-1000)

pts=[(t[2*i],t[2*i+1]) for i in range(500)]
m=0.0
c=0

for x,y in pts:
    sub=sorted([(a-x,b-y) for a,b in pts if b>y or (b==y and a>x)], key=lambda u:math.atan2(u[1],u[0]))
    d=[[0]*500 for i in range(500)]
    for i in range(len(sub)):
        j=i-1
        while j>=0 and sub[i][0]*sub[j][1]==sub[i][1]*sub[j][0]:
            j-=1
        flag=(j==i-1)
        while j>=0:
            k=j-1
            while k>=0 and ((sub[i][0]-sub[j][0])*(sub[k][1]-sub[j][1])-(sub[i][1]-sub[j][1])*(sub[k][0]-sub[j][0]))<0:
                k-=1
            s=abs(sub[i][0]*sub[j][1]-sub[i][1]*sub[j][0])
            if k>=0:
                s+=d[j][k]
            if flag:
                d[i][j]=s
            m=max(m,s)
            j=k
        if flag:
            for j in range(1,i):
                d[i][j]=max(d[i][j],d[i][j-1])
    c+=1
    if c%5==0:print c/5,"percent completed, current max:",0.5*m

print 0.5*m