AtCoder Regular Contest 082 E - ConvexScore

题意

对于每一个凸多边形的顶点集S，定义其权值为$2^{|n|?|S|}$
，$n$为凸包内的点集。求所有$S$的权值和。

题解

栋老师模拟赛的题。。
之前用的是题解的方法

这样就是$O(n^3)$，代码比较简单，这里就不放出来了

但是感觉这种凸包DP还是十分经典
不得不学一下
这题当然也是可以用凸包DP
普通的凸包DP是$O(n^4)$的
大概就是，我们先枚举凸包最下的一个点$\text{t}mp$
然后像凸包一样排序
然后$f_{i,j}$表示最后两个点是$i,j$的答案是多少
至于转移，就是找到一个点k，使得$k$和$tmp$在$(i,j)$的同一个半平面内
也就是$tmp,i,j,k$可以形成一个凸包
转移到$f_{i,j}$可以转移到$f_{j,k}$
直接这么做就是$O(n^4)$的啦
你可以把这个过程想象成每一次加入一个三角形，不断把这个凸包拼出来
当然，你要预处理一个一下$g_{i,j}$，表示$tmp,i,j$这个三角形里面有多少个点
这个的话，你可以$O(n^4)$预处理，也可以$O(n^{3}logn)$预处理
我比较偷懒就写了$O(n^4)$的

再说一下这个凸包DP，看起来是$O(n^4)$的
但是可以观察到，如果我们先枚举j，然后把$i$，$k$按关于$j$的极角排序
那么对于$i$递增，$k$都是连续的一段后缀
因此，排完序以后，可以单调地扫过去，就可以做到就可以省去一个$n$啦
那么这个部分就是$O(n^3)$的
瓶颈在于排序$O(n^{3}logn)$，但是排序也可以预处理，那么凸包DP的整个过程就可以在$O(n^3)$解决了
那么复杂度瓶颈就在于g了，然而我并不知道怎么优化这个g

下面给出代码（排序没有预处理的）
CODE:

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int MOD=998244353;
const int N=205;
int n;
struct qq
{
    int x,y;void print ()	{
    printf("%d %d\n",x,y);}
}a[N],b[N];
int tot;
int ans;
qq tmp;
int mul (qq x,qq y,qq z)
{
    int x1=x.x-z.x,y1=x.y-z.y;int x2=y.x-z.x,y2=y.y-z.y;return x1*y2-x2*y1;
}
int dis (qq x,qq y)	{
    return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);}
bool cmp (qq x,qq y)
{
    if (mul(x,y,tmp)==0) return dis(x,tmp)<dis(y,tmp);return mul(x,y,tmp)>0;
}
bool cmp1 (int x,int y)
{
    if (mul(b[x],b[y],tmp)==0) return dis(b[x],tmp)<dis(b[y],tmp);return mul(b[x],b[y],tmp)>0;
}
bool check (qq x,qq y,qq z)//z是否在 (tmp,x,y)
{
    if (mul(z,x,tmp)==0) return false;if (mul(z,y,x)>0) return false;return true;
}
int f[N][N];
int g[N][N];
int mul (int x,int y)	{
    return (LL)x*y%MOD;}
int add (int x,int y)	{
    x=x+y;return x>=MOD?x-MOD:x;}
int id[N],id1[N];
int m,m1;
int Pow[N];
void solve (int x)
{
    //printf("solve:%d\n",x);tot=0;tmp=a[x];for (int u=1;u<=n;u++){
    if (a[u].y>a[x].y||(a[u].y>=a[x].y&&a[u].x>=a[x].x))	b[++tot]=a[u];}sort(b+1,b+1+tot,cmp);for (int u=1;u<=tot;u++)	for (int i=1;i<=tot;i++)g[u][i]=f[u][i]=0;/*for (int u=1;u<=tot;u++)for (int i=u+1;i<=tot;i++){int lalal=0;for (int k=u+1;k<i;k++){if (mul(b[k],b[u],tmp)==0) continue;if (mul(b[k],b[i],b[u])<=0) lalal++;}g[u][i]=Pow[lalal];}*/for (int u=1;u<=tot;u++)for (int i=u+1;i<=tot;i++)g[u][i]=1;for (int u=1;u<=tot;u++)for (int k=u+1;k<=tot;k++){
    if (mul(b[k],b[u],tmp)==0) continue;for (int i=k+1;i<=n;i++){
    if (mul(b[k],b[i],b[u])<=0)g[u][i]=add(g[u][i],g[u][i]);}}for (int u=2;u<=tot;u++){
    f[1][u]=1;for (int i=2;i<u;i++)if (mul(b[i],b[u],b[1])==0)f[1][u]=add(f[1][u],f[1][u]);}for (int i=2;i<=tot;i++){
    //printf("i:%d\n",i);m=0;m1=0;for (int u=1;u<i;u++)	id[++m]=u;for (int u=i+1;u<=tot;u++) id1[++m1]=u;tmp=b[i];sort(id+1,id+1+m,cmp1);sort(id1+1,id1+1+m1,cmp1);int now=1,k=m1,sum=0;for (int u=1;u<=m1;u++){
    while (now<=m&&mul(b[id1[u]],b[i],b[id[now]])<0){
    sum=add(sum,f[id[now]][i]);now++;}f[i][id1[u]]=add(f[i][id1[u]],mul(sum,g[i][id1[u]]));}}for (int u=2;u<=tot;u++)for (int i=u+1;i<=tot;i++)ans=add(ans,f[u][i]);
}
int main()
{
    freopen("c.in","r",stdin);freopen("c.out","w",stdout);scanf("%d",&n);Pow[0]=1;for (int u=1;u<=n;u++) Pow[u]=add(Pow[u-1],Pow[u-1]);for (int u=1;u<=n;u++)	scanf("%d%d",&a[u].x,&a[u].y);for (int u=1;u<=n;u++) solve(u);printf("%d\n",ans);return 0;
}