【省选模拟】多边形（凸包DP）

• 钦定一个点为起点，令 $f_{i,j}$fi,j​ 表示凸包的最后两个点为 $i,j$i,j 的方案数。
  枚举 $k$k 转移到 $f_{k,i}$fk,i​ 需要满足 $\triangle pik$△pik 中没有点，按叉积预处理与原点形成的三角形包涵的点数后就可以 $O(n^4)$O(n4) 做，发现这个可以前缀和优化，按与 $i$i 形成的极角排序，那么对于 $k$k 合法的转移是一个前缀，双指针扫一遍，于是就可以做到 $O(n^3)$O(n3)

#include<bits/stdc++.h>
#define cs const
using namespace std;
int read(){
	int cnt = 0, f = 1; char ch = 0;
	while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1; }
	while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar();
	return cnt * f;
}
cs int N = 505;
cs int Mod = 1e9 + 7;
int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b; }
int mul(int a, int b){ return 1ll * a * b % Mod; }
int dec(int a, int b){ return a - b < 0 ? a - b + Mod : a - b; }
void Add(int &a, int b){ a = add(a, b); }
void Mul(int &a, int b){ a = mul(a, b); }
struct Pnt{
	int x, y; Pnt(int _x=0, int _y=0){ x = _x; y = _y; }
	Pnt operator + (cs Pnt &a){ return Pnt(x+a.x,y+a.y); }
	Pnt operator - (cs Pnt &a){ return Pnt(x-a.x,y-a.y); }
	int operator * (cs Pnt &a){ return x*a.y-y*a.x; }
}p[N];
bool cmp(Pnt a, Pnt b){ return a.y==b.y?a.x<b.x:a.y<b.y; }
int n, ps[N][N<<1];
int dp[N][N], Cons;
int Cross(int a, int b, int c){ return (p[a]-p[c])*(p[b]-p[c]); }
bool comp(int a, int b){ return Cross(a,b,Cons) > 0; } 
int main(){
	n = read();
	for(int i=1; i<=n; i++) p[i].x=read(), p[i].y=read();
	sort(p+1, p+n+1, cmp);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++) ps[i][j]=j;
		ps[i][i]=1; Cons=i;
		sort(ps[i]+2, ps[i]+i+1, comp);
		sort(ps[i]+i+1, ps[i]+n+1, comp);
		for(int j=n+1; j<n+n; j++) ps[i][j] = ps[i][j-n+1];
	} 
	int ans = 0;
	for(int i=1; i<=n; i++){
		memset(dp,0,sizeof(dp));
		for(int j=i+1; j<=n; j++){
			static int ql[N],qr[N]; int tl=0, tr=0, nx=ps[i][j], p=0;
			for(int k=2; k<=n; k++) if(ps[nx][k]==i){ p=k; break; }
			for(int k=p; k<p+n; k++){
				if(Cross(ps[nx][k],i,nx)>0) qr[++tr]=ps[nx][k];
				else ql[++tl]=ps[nx][k];
			} 
			int sm=0, l=1, r=1;
			while(r<=tr){
				if(l>tl||Cross(qr[r],ql[l],nx)<0) 
				Add(dp[nx][qr[r]],sm), ++r;
				else Add(sm,dp[ql[l]][nx]), ++l;
			}
			int pre=0;
			while(tr){
				if(!pre||Cross(qr[tr],pre,i)>0)
				Add(dp[nx][qr[tr]],1), pre=qr[tr];
				else dp[nx][qr[tr]]=0; tr--;
			}
			for(int k=j+1; k<=n; k++) Add(ans,dp[nx][ps[i][k]]);
		}
	} cout<<ans; return 0;
}