USACO Section 3.1 Shaping Regions - 矩阵切割..

USACO Section 3.1 Shaping Regions - 矩阵切割..

开始听对里的大大说这是二维线段树..没敢写..后来再一想..数据范围N<=2500..那么N^2的算法可以过...再一想...其实就是拿到一个矩阵然后和以后填上去的矩阵来比较..去掉重合的部分..将矩阵切割成若干小矩阵..然后这些小矩阵再继续往后面看有没有和后面填的矩阵重合的矩形区域(矩形和矩形重合的区域也一定是矩形)..有的做相同的操作...后来才知道这就是矩阵切割..时间复杂度是N^2..可以接受..用递归来实现很方便..递归时我就假想当前矩阵的重复区域矩形是在当前这个矩形内部的..那么为了切掉这个重复的中间部分..那么我要把这个矩形切成四块.如图:

就让他这么切..为了防止一些切出来不满足要求或者切出来面积为0没有意义的区域..那么就在递归的时候加个判断.看当前的矩形是否是合法的..也就是lx

Program:

/* ID: zzyzzy12 LANG: C++ TASK: rect1*/ #include #include#include #include #include #include#include #include #define oo 2000000000#define ll long longusing namespace std; struct node{ int lx,ly,ux,uy,color; }s[5510],a[50001];int ans[2510],A,B,N,i,num; void cut(node h,int m){ int i,lx,ly,ux,uy; node k; if (h.lx>=h.ux || h.ly>=h.uy) return; for (i=m+1;i<=N;i++) if (!(s[i].lx>=h.ux || s[i].ux<=h.lx || s[i].ly>=h.uy || s[i].uy<=h.ly)) break; if (i>N) { a[++num]=h; return; } if (h.lx>=s[i].lx && h.ux<=s[i].ux && h.ly>=s[i].ly && h.uy<=s[i].uy) return; lx=max(s[i].lx,h.lx); ly=max(s[i].ly,h.ly); ux=min(s[i].ux,h.ux); uy=min(s[i].uy,h.uy); //----------------- k=h; k.lx=ux; cut(k,i); k=h; k.ux=lx; cut(k,i); k=h; k.ly=uy; k.lx=lx; k.ux=ux; cut(k,i); k=h; k.uy=ly; k.lx=lx; k.ux=ux; cut(k,i); //----------------- return;}int main(){ freopen("rect1.in","r",stdin); freopen("rect1.out","w",stdout); memset(ans,0,sizeof(ans)); scanf("%d%d%d",&A,&B,&N); for (i=1;i<=N;i++) scanf("%d%d%d%d%d",&s[i].lx,&s[i].ly,&s[i].ux,&s[i].uy,&s[i].color); s[0].lx=s[0].ly=0; s[0].ux=A; s[0].uy=B; s[0].color=1; num=0; for (i=N;i>=0;i--) cut(s[i],i); for (i=1;i<=num;i++) ans[a[i].color]+=(a[i].ux-a[i].lx)*(a[i].uy-a[i].ly); for (i=1;i<=2500;i++) if (ans[i]) printf("%d %d\n",i,ans[i]); return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。