题解：P17067 [ICPC 2017 Shenyang R] Empty Convex Polygons
lailai0916
·
·
题解
题意简述
从给定整点中选择若干点作为凸多边形顶点。
多边形内部不能包含任何给定点，但边界上可以有点。
求满足条件的最大面积。
解题思路
全程计算面积的两倍。
定义有向叉积：
C(a,b,c)=(b-a)\times(c-a)
枚举凸多边形中按 (y,x) 字典序最小的顶点 O。
其余顶点的纵坐标更大，
或与 O 同高且位于右侧。
将所有这样的点绕 O 按极角递增排序为：
P_1,P_2,\dots,P_m
同一条边上的共线顶点可以从顶点序列中删除，
多边形形状、面积与内部点集都不会改变。
因此，只需枚举转角严格为正的凸多边形。
对每条有向直线 a\to b，
用一个 64 位整数 side[a][b] 记录严格位于其左侧的给定点。
因为 n\le50，一个二进制位便能表示一个点。
当 C(a,b,c)>0 时，点严格位于三角形 abc 内部，
当且仅当它同时位于三条有向边的左侧。
所以三角形内部为空等价于：
L_{a,b}\cap L_{b,c}\cap L_{c,a}=\varnothing
代码只需对三个 64 位集合执行按位与。
三角形边界上的点不在严格左侧集合的交中，
与题目允许边界点的条件一致。
扇形剖分还会产生从 O 出发的内部对角线。
若某个给定点位于这种对角线内部，
它虽然在相邻两个三角形的边界上，
却位于整个多边形内部，必须排除。
因此预处理 clear[a][b]，
表示线段 ab 的开区间内没有给定点。
动态规划直接使用原点编号作为下标。
设 u=P_i,v=P_j 且 i<j。
末尾两个多边形顶点为 $u,v$ 时的最大两倍面积。
若 $C(O,u,v)>0$ 且三角形 $Ouv$ 内部为空，
它自身可以构成一个状态：
$$
f_{u,v}=C(O,u,v)
$$
再枚举 $w=P_k$，其中 $k<i$。
若 $f_{w,u}$ 存在，$C(w,u,v)>0$，
并且内部对角线 $Ou$ 的开区间没有给定点，
就可以加入新的扇形三角形：
$$
f_{u,v}=\max\left(f_{u,v},f_{w,u}+C(O,u,v)\right)
$$
极角顺序保证新增边不会与已有边交叉。
正叉积保证每个多边形转角严格凸。
新三角形内部为空，旧边 $Ou$ 变成内部对角线时也没有给定点，
所以转移始终保持凸洞条件。
反过来，取任意凸洞并删除共线冗余顶点。
选择其字典序最小顶点 $O$ 后，
其余顶点必按上述极角顺序出现。
从 $O$ 作扇形剖分，
若某个给定点位于凸洞内部，
它必严格位于某个扇形三角形内，
或位于某条内部对角线的开区间内。
凸洞排除了这两种情况，
所以它的每一步都能由上述状态和转移表示。
枚举所有 $O$ 后，动态规划覆盖全部严格凸洞，
也就覆盖删去冗余共线点后的所有凸洞。
因此，取全部状态的最大值即可得到答案。
左侧点集与线段开区间状态需要 $O(n^3)$ 预处理。
枚举 $O,i,j,k$ 的动态规划需要 $O(n^4)$ 时间，空间复杂度为 $O(n^2)$。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
const int N=55;
struct point
{
int x,y;
}p[N];
int root,ord[N],f[N][N];
ull side[N][N];
bool clear[N][N];
int cross(point a,point b,point c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int len(point a,point b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool cmp(int x,int y)
{
int z=cross(p[root],p[x],p[y]);
return z?z>0:len(p[root],p[x])<len(p[root],p[y]);
}
bool empty(int a,int b,int c)
{
return !(side[a][b]&side[b][c]&side[c][a]);
}
void solve()
{
int n;
cin>>n;
for(int i=0;i<n;i++)cin>>p[i].x>>p[i].y;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
side[i][j]=0;
clear[i][j]=1;
for(int k=0;k<n;k++)
{
int z=cross(p[i],p[j],p[k]);
if(z>0)side[i][j]|=1ull<<k;
if(k!=i&&k!=j&&z==0&&(p[k].x-p[i].x)*(p[k].x-p[j].x)+(p[k].y-p[i].y)*(p[k].y-p[j].y)<0)clear[i][j]=0;
}
}
int ans=0;
for(root=0;root<n;root++)
{
int m=0;
for(int i=0;i<n;i++)
if(p[i].y>p[root].y||(p[i].y==p[root].y&&p[i].x>p[root].x))ord[m++]=i;
sort(ord,ord+m,cmp);
memset(f,0,sizeof f);
for(int i=0;i<m;i++)
{
int u=ord[i];
for(int j=i+1;j<m;j++)
{
int v=ord[j];
int s=cross(p[root],p[u],p[v]);
if(s<=0||!empty(root,u,v))continue;
f[u][v]=s;
if(clear[root][u])
for(int k=0;k<i;k++)
{
int w=ord[k];
if(f[w][u]&&cross(p[w],p[u],p[v])>0)f[u][v]=max(f[u][v],f[w][u]+s);
}
ans=max(ans,f[u][v]);
}
}
}
cout<<ans/2<<'.'<<ans%2*5<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
while(T--)solve();
return 0;
}
```