一条边能连上当且仅当它没有经过任何点,并且两边的点都是偶数个。

枚举原点,通过极角排序求出哪些边是合法的,然后区间DP即可。

时间复杂度$O(nm\log m+n^3)$。

#include<cstdio>
#include<algorithm>
const int N=610,M=20010;
int n,m,P,cnt,i,j,k,t,now,f[N][N];bool g[N][N],v[N][N];
struct vec{
int x,y,p;
vec(){}
vec(int _x,int _y){x=_x,y=_y;}
vec operator-(const vec&b){return vec(x-b.x,y-b.y);}
}a[N],b[M],c[N+M],O;
inline int cross(vec a,vec b){return a.x*b.y-a.y*b.x;}
inline bool cmp(vec x,vec y){return cross(x-O,y-O)<0;}
int dp(int l,int r){
if(l+1==r)return 1;
if(v[l][r])return f[l][r];
v[l][r]=1;
int&t=f[l][r];
for(int i=l+1;i<r;i++)if(g[i][l]&&g[i][r])t=(t+dp(l,i)*dp(i,r))%P;
return t;
}
int main(){
scanf("%d%d%d",&n,&m,&P);
for(i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);
for(i=1;i<=m;i++)scanf("%d%d",&b[i].x,&b[i].y);
O=a[1];
std::sort(a+2,a+n+1,cmp);
for(i=1;i<=n;i++)a[i].p=i;
for(i=1;i<=n;i++){
O=a[i];
cnt=0;
for(j=1;j<=n;j++)if(j!=i)c[++cnt]=a[j];
for(j=1;j<=m;j++)c[++cnt]=b[j];
std::sort(c+1,c+cnt+1,cmp);
for(j=1,t=0;j<=cnt;j=k){
for(now=0,k=j;k<=cnt&&!cross(c[k]-O,c[j]-O);k++)if(!c[k].p)now++;
if(!now&&!t)for(k=j;k<=cnt&&!cross(c[k]-O,c[j]-O);k++)if(c[k].p)g[i][c[k].p]=g[c[k].p][i]=1;
t^=now&1;
}
}
return printf("%d",dp(1,n)),0;
}

  

最新文章

  1. 用Java来写常见的排序算法
  2. windows 内部预览版与迅雷极速版不配合
  3. 运用CSS和JS写的大图轮播-带箭头
  4. perl备忘
  5. RabbitMQ介绍4 - 编程(C#客户端示例)
  6. 这些小众软件让你的效率提升N倍!(必备,收藏)
  7. 由.Net类库提供的农历计算(C#农历)-获取当前日期的农历日期
  8. 一行代码实现iOS序列化与反序列化(runtime)
  9. RecyclerView 详解
  10. 【SICP读书笔记(一)】正则序展开的特殊情况
  11. 一场完美的“秒杀”:API加速的业务逻辑
  12. “百度杯”CTF比赛(二月场)-web-writeup
  13. TCP/IP ARP
  14. kubernetes资源类别介绍
  15. 黄聪:谷歌验证 (Google Authenticator) 的实现原理是什么?
  16. Weex学习资料整合
  17. mybatis的sqlSessionFactory的加载过程
  18. 理解套接字Socket
  19. Java之File类详解
  20. Innodb表压缩过程中遇到的坑(innodb_file_format)

热门文章

  1. (转)MySQL索引原理及慢查询优化
  2. Oracle开机自启动
  3. 【Bootstrap】Bootstrap-select多选下拉框实现
  4. tyvj1011 传纸条
  5. (五)SQL Server分区自动化案例
  6. ecshop商品详情相册顺序调整
  7. js框架设计1.3数组化
  8. 【krpano】krpano xml资源解密(破解)软件说明与下载(v1.3)
  9. servlet 之 response 回复 字节流 字符流
  10. Shell 编程 : 数值,字符,字符串