不难猜到或者发现的性质，如果连了一条对角线划分出了奇数个点，那么这条对角线肯定不合法；因为划分成三角形就不可能有对角线相交，于是划分成奇数的那一边怎么样也不可能划分成全是偶数
于是我们需要对每一条对角线求，有多少条个点在它上面，直接暴力枚举对角线用叉积来判是(O(n^2m))的，显然过不去的样子；不难发现这个问题具有一定的单调性，对于一个点(i)，求凸包上其他点(j)和(i)所连对角线的划分情况，我们可以顺时针枚举点(j)，不难发现如果一个点在((i,j-1))这条边以上，那么也肯定在((i,j))以上，于是我们以点(i)为原点跑一边奇角排序，之后开个指针扫一扫就好了
之后求方案数就比较简单了，这是一个凸多边形的弦划分问题，可以大力区间(dp)
设(g_{l,r})表示区间([l,r])的合法划分数
那么就有(g_{l,r}=sum_{i=l+1}^{r-1}[f_{l,i}=1][f_{i,r}=1]g_{l,i} imes g_{i,r})
(f_{l,i}=1)表示这条对角线合法
复杂度是(O(nmlog m+n^3))，代码
#include<bits/stdc++.h>
#define vt pt
#define re register
inline int read() {
char c=getchar();int x=0,r=1;while(c<'0'||c>'9') {if(c=='-') r=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x*r;
}
const int maxn=603;
struct pt {int x,y;}a[maxn],b[200005];
int n,m,mod,nw;
int f[maxn][maxn],g[maxn][maxn],vis[maxn][maxn];
inline int qm(int x) {return x>=mod?x-mod:x;}
inline int crs(pt A,pt B) {return A.x*B.y-A.y*B.x;}
inline vt operator-(const pt A,const pt B) {return (vt){A.x-B.x,A.y-B.y};}
inline int cmp(const vt A,const vt B) {return crs(A-a[nw],B-a[nw])<0;}
int dfs(int l,int r) {
if(vis[l][r]) return g[l][r];
vis[l][r]=1;
for(re int i=l+1;i<r;i++)
if(!(f[l][i]|f[i][r])) g[l][r]=qm(g[l][r]+dfs(l,i)*dfs(i,r)%mod);
return g[l][r];
}
int main() {
n=read(),m=read(),mod=read();
for(re int i=1;i<=n;i++) a[i].x=read(),a[i].y=read();
for(re int i=1;i<=m;i++) b[i].x=read(),b[i].y=read();
for(re int i=1;i<=n;i++) {
nw=i;std::sort(b+1,b+m+1,cmp);int tot=0;
for(re int j=i+1;j<=n;j++) {
while(tot<m&&crs(a[j]-a[i],b[tot+1]-a[i])>=0) ++tot;
f[i][j]=f[j][i]=(tot&1);
if(tot&&crs(a[j]-a[i],b[tot]-a[i])==0) f[i][j]=f[j][i]=1;
}
}
for(re int i=1;i<n;i++) g[i][i+1]=1,vis[i][i+1]=1;
printf("%d
",dfs(1,n));
return 0;
}