矩形切割与动态统计问题地一些ACM例题.doc

实用标准文档矩形切割与动态统计问题 矩形切割具体思想见薛矛的解决动态统计问题的两把利刃矩形切割例题：（POJ：2528、3277、1151、1389、1177）POJ 2528：Mayors poster/题意：贴海报（后一张海报一定不会被前面的海报覆盖），海报覆盖区域用x,y区间表示，问最后有多少张海报是没被完全覆盖的。Code： #include #include using namespace std; #define maxn 10005 struct NODE int x,y; int ans; nodemaxn; int n; void cover(int l,int r,int k,int c) while(kn&(rnodek.y) /完全不覆盖 k+; if(k=n) /if(k=n|(r-l+1=0) nodec.ans+=r-l+1; return; if(lnodek.y) /左边部分被覆盖 cover(nodek.y+1,r,k+1,c); /r=nodek.y; int main() int t,i,j,sum; scanf(%d,&t); while(t-) sum=0; memset(node,0,sizeof(node); scanf(%d,&n); for(i=0;i=0;i-)cover(nodei.x,nodei.y,i+1,i); for(i=0;i0) sum+; printf(%dn,sum); return 0; /*Sample Input151 42 68 103 47 10Sample Output4*/POJ 3277：City Horizon/题意：一些大楼都在地平线上，求这些大楼倒影覆盖总面积。/分析：水平线上被覆盖的部分肯定记录到高度大的部分，所以按大楼高度升序排序。Code： #include #include #include using namespace std; #define maxn 40005 struct NODE _int64 x1,x2,y,ans; nodemaxn; int n; bool cmp(NODE a,NODE b) if(a.y!=b.y) return a.yb.y; /因为是面积和的问题，所以宽高的肯定应该放在后面，低的算被覆盖 else if(a.x2!=b.x2) return a.x2b.x1; void cover(_int64 l,_int64 r,int k,int c) while(kn&(rnodek.x2) k+; if(k=n|(r-l=0) nodec.ans+=r-l; return; if(lnodek.x2) cover(nodek.x2,r,k+1,c); int main() int i,j; memset(node,0,sizeof(node); scanf(%d,&n); for(i=0;i=0;i-) cover(nodei.x1,nodei.x2,i+1,i); _int64 sum=0; for(i=0;i=1) sum+=nodei.ans*nodei.y; printf(%I64dn,sum); /*Sample Input42 5 1 （数据分别为水平线上起点和终点，楼的高度）9 10 46 8 24 6 3Sample Output16*/POJ 1151：Atlantis（矩形面积并）/法1：离散化（本题数据量为100以内）。离散化后坐标纸上最大为100*100的网格，将被覆盖的网格标记为true，之后直接扫描统计即可。Code： #include #include #include #include #include using namespace std; #define maxn 205 struct NODE double x1,y1,x2,y2; nodemaxn; double xmaxn,ymaxn; bool mapmaxnmaxn; int main() int n,i,j,k,t=0; while(scanf(%d,&n),n) int m=0; for(i=0;in;i+) scanf(%lf%lf%lf%lf,&nodei.x1,&nodei.y1,&nodei.x2,&nodei.y2); xm=nodei.x1;ym=nodei.y1; m+; xm=nodei.x2;ym=nodei.y2; m+; /printf(m=%dn,m); sort(x,x+m); sort(y,y+m); memset(map,false,sizeof(map); int x1,x2,y1,y2; for(i=0;in;i+) /离散化 for(j=0;jm;j+) if(fabs(xj-nodei.x1)=1e-6) x1=j; break; for(j=0;jm;j+) if(fabs(xj-nodei.x2)=1e-6) x2=j; break; for(j=0;jm;j+) if(fabs(yj-nodei.y1)=1e-6) y1=j; break; for(j=0;jm;j+) if(fabs(yj-nodei.y2)=1e-6) y2=j; break; for(j=x1;jx2;j+) for(k=y1;ky2;k+) mapjk=true; printf(Test case #%dn,+t); double ans=0.0; for(i=0;im-1;i+) for(j=0;jm-1;j+) if(mapij) /被覆盖的求出面积ans+=(xi+1-xi)*(yj+1-yj); printf(Total explored area: %.2lfnn,ans); return 0; /法2：普通矩形切割法。将每个矩形着色，假设后面的矩形颜色一定不会被前面的矩形颜色覆盖。最后扫描个每种颜色覆盖的区域。总和便是所求。Code： #include #include #include #include using namespace std; #define maxn 105 struct NODE double x1,y1,x2,y2; int color; nodemaxn; double mapmaxn; int n; void cover(double x1,double y1,double x2,double y2,int c,int k) while(knodek.x2|x2nodek.y2|y2=n|(fabs(x2-x1)1e-6)|(fabs(y2-y1)1e-6) mapc+=(x2-x1)*(y2-y1); return; if(x1=nodek.x2) /偏右 cover(nodek.x2,y1,x2,y2,c,k+1); x2=nodek.x2; if(y1=nodek.y2) /偏上 cover(x1,nodek.y2,x2,y2,c,k+1); y2=nodek.y2; int main() int i,t=0; while(scanf(%d,&n),n) t+; for(i=0;i=0;i-) cover(nodei.x1,nodei.y1,nodei.x2,nodei.y2,nodei.color,i+1); double ans=0.0; for(i=0;i1e-6) ans+=mapi; printf(Test case #%dnTotal explored area: %.2lfnn,t,ans); return 0; /*Sample Input210 10 20 2015 15 25 25.50Sample OutputTest case #1Total explored area: 180.00 */POJ 1177：（矩形周长并，括号匹配+矩形切割）/分析：（括号匹配）首先把矩形的上边界作为“左括号”边，下边界作为“右括号”边，然后上下排序。假定排完序之后是下面的状态：()()()()()考虑“最外侧”的括号的数量。显然上面的那个串是() & () & ()()()有六个最外侧括号，那么边界数量就是6。排序的复杂度O(nlogn)，对于上面的思路，针对横边来说，如果并不是完全包括的怎办，那就是将边分割成一些小段在用括号匹配。 括号匹配用到此题恰到好处即在于可以有效处理掉重复覆盖避免重复计算边的问题。因为先将每个矩形的上、下边附一个标号1、-1。而对于此题有一个性质是，无论矩形怎么覆盖，最终对于某一小段边一定会有一个对应的边存在。那么1、-1正好起到匹配的作用。Code： #include #include #include using namespace std; #define maxn 10005 struct NODE int cankao,weizhi,st,en; /weizhi为表明匹配边 nodexmaxn,nodeymaxn; int mapx2*maxn,mapy2*maxn,lenxmaxn,lenymaxn,vistmaxn; bool cmp(NODE n1,NODE n2) return n1.cankaon2.cankao; int main() int n,i,j,x1,y1,x2,y2; memset(mapx,0,sizeof(mapx); memset(mapy,0,sizeof(mapy); scanf(%d,&n); for(i=0;in;i+) /存信息 scanf(%d%d%d%d,&x1,&y1,&x2,&y2); x1+=maxn;y1+=maxn;x2+=maxn;y2+=maxn; mapxx1=mapxx2=mapyy1=mapyy2=1; nodex2*i.cankao=y1;nodex2*i.weizhi=1;nodex2*i.st=x1;nodex2*i.en=x2;nodex2*i+1.cankao=y2;nodex2*i+1.weizhi=-1;nodex2*i+1.st=x1;nodex2*i+1.en=x2; nodey2*i.cankao=x1;nodey2*i.weizhi=1;nodey2*i.st=y1;nodey2*i.en=y2;nodey2*i+1.cankao=x2;nodey2*i+1.weizhi=-1;nodey2*i+1.st=y1; nodey2*i+1.en=y2; stable_sort(nodex,nodex+2*n,cmp); stable_sort(nodey,nodey+2*n,cmp); int tmpx=0,tmpy=0,ans=0; for(i=0;i2*maxn;i+) if(mapxi) mapxi=tmpx; lenxtmpx+=i; if(mapyi) mapyi=tmpy; lenytmpy+=i; for(i=0;i2*n;i+) /离散化 nodexi.st=mapxnodexi.st; nodexi.en=mapxnodexi.en; nodeyi.st=mapynodeyi.st; nodeyi.en=mapynodeyi.en; memset(vist,0,sizeof(vist); for(i=0;i2*n;i+) for(j=nodexi.st;jnodexi.en;j+) vistj+=nodexi.weizhi; if(vistj=0) /匹配成功 ans+=lenxj+1-lenxj; memset(vist,0