首页 > 代码库 > POJ 3695
POJ 3695
可以用容斥原理来求。求两个矩形的并的时候可以使用条件
x1=max(p.x1,q.x1);
y1=max(p.y1,q.y1);
x2=min(p.x2,q.x2);
y2=min(p.y2,q.y2);
而
if(x2>x1&&y2>y1)可以并,否则,并不了。
。。。
开始时,我对每个询问都做一次容斥原理,TLE。可以这样改进一下。对每个询问,用了哪些矩形可以用一个二进制的数来存起来。对所有的矩形做一次DFS,然后判断当一个组合内的矩形均属于某个询问内(可用二进制或计算),则按照容斥原理公式计算即可。
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define M 100005using namespace std;struct Rectangle{ int x1,y1,x2,y2;};Rectangle r[25];int status[1250000];int choice[M];int ans;bool WhetherRec(int x1,int y1,int x2,int y2){ if(x2>x1&&y2>y1) return true; return false;}void dfs(int i,int num,Rectangle p,int al,int sta,int ml){ if(i>=al){ if(num==0){ for(int k=1;k<=ml;k++) status[choice[k]]=0; } else if(num&1){ for(int k=1;k<=ml;k++){ if((sta|choice[k])<=choice[k]) status[choice[k]]+=(p.x2-p.x1)*(p.y2-p.y1); } } else{ for(int k=1;k<=ml;k++){ if((sta|choice[k])<=choice[k]) status[choice[k]]-=(p.x2-p.x1)*(p.y2-p.y1); } } return ; } dfs(i+1,num,p,al,sta,ml); Rectangle tmp; int x1=max(p.x1,r[i].x1); int y1=max(p.y1,r[i].y1); int x2=min(p.x2,r[i].x2); int y2=min(p.y2,r[i].y2); if(WhetherRec(x1,y1,x2,y2)){ tmp.x1=x1; tmp.x2=x2; tmp.y1=y1; tmp.y2=y2; dfs(i+1,num+1,tmp,al,sta|(1<<(i)),ml); }}void work(int n,int m){ Rectangle p; p.x1=p.y1=0; p.x2=p.y2=1000; dfs(0,0,p,n,0,m);}int main(){ int kase=0; int n,m,k,tmp,sta; while(scanf("%d%d",&n,&m),n||m){ kase++; for(int i=0;i<n;i++) scanf("%d%d%d%d",&r[i].x1,&r[i].y1,&r[i].x2,&r[i].y2); for(int i=1;i<=m;i++){ scanf("%d",&k); sta=0; for(int p=0;p<k;p++){ scanf("%d",&tmp); sta=(sta|(1<<(tmp-1))); } choice[i]=sta; } work(n,m); printf("Case %d:\n",kase); for(int e=1;e<=m;e++){ printf("Query %d: %d\n",e,status[choice[e]]); } printf("\n"); } return 0;}
POJ 3695
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。