[关键字]：数据结构 线段树 扫描法
[题目大意]：给出n个矩形的左下角和右上角，求出所有矩形面积的并。
//==========================================================================
[分析]：可以用扫描法来求，首先将所有y值离散化然后建立线段树（用来求所有竖直的边的并），在把所有矩形都变成两条线——左边和右边，然后左边需要被加入线段树，右边代表退出线段树，并以x为关键字排序。从左到右枚举每一个边加入这样当前边的x1和上一条加入的边x2之间一定是一个矩形，而这个矩形的一边是x2-x1，另一边就是所有在线段树中的边的并，这样只要把每个这样的举行面积相加就行了。而求线段的并这是线段树的一个基本操作：开一个cov域记录当前节点所代表的区间的是否被完整覆盖，在开一个域len记录当前节点所代表的区间的线段的并是多少，cov可以再插入时更改：如果是左边cov+1否则-1，而len的维护：如果cov>0len=区间长度，否则如果是叶子len=0如果不是叶子len=左儿子的len+右儿子的len的和。
[代码]：
View Code #include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>using namespace std;const int MAXN=100000;struct node{int x,y1,y2,flag;}line[3000];struct rec{int l,r,lc,rc,len,cov,x,y;}tree[MAXN];int tot,t,n;int y[3200],yy[3000];bool cmp(node a,node b){return a.x<b.x;}void Build(int l,int r){int now=++tot; tree[now].x=l,tree[now].y=r; tree[now].l=y[l],tree[now].r=y[r]; tree[now].len=tree[now].cov=tree[now].lc=tree[now].rc=0;if (tree[now].x+1<tree[now].y) { tree[now].lc=tot+1; Build(l,(l+r)/2); tree[now].rc=tot+1; Build((l+r)/2,r); }}void Update(int v){if (tree[v].cov>0) { tree[v].len=tree[v].r-tree[v].l;return; }if (tree[v].x+1==tree[v].y) tree[v].len=0; else tree[v].len=tree[tree[v].lc].len+tree[tree[v].rc].len;}void Insert(int v,node a){if (tree[v].l==a.y1 && tree[v].r==a.y2) { tree[v].cov+=a.flag; Update(v);return; }if (tree[tree[v].lc].r>=a.y2) Insert(tree[v].lc,a); elseif (tree[tree[v].rc].l<=a.y1) Insert(tree[v].rc,a); else { node temp=a; temp.y2=tree[tree[v].lc].r; Insert(tree[v].lc,temp); temp=a; temp.y1=tree[tree[v].rc].l; Insert(tree[v].rc,temp); } Update(v);//printf("%d %d %d %d %d %d\n",v,tree[v].l,tree[v].r,a.y1,a.y2,tree[v].len);}void Debug(int v){if (!v) return; printf("%d %d\n",tree[v].l,tree[v].r); Debug(tree[v].lc); Debug(tree[v].rc);}bool Init(){int x1,y1,x2,y2,temp=0; tot=0;while (scanf("%d%d%d%d",&x1,&y1,&x2,&y2),x1!=-1) { line[++temp].x=x1,line[temp].y1=y1,line[temp].y2=y2,line[temp].flag=1,yy[temp]=y1; line[++temp].x=x2,line[temp].y1=y1,line[temp].y2=y2,line[temp].flag=-1,yy[temp]=y2; }if (!temp) return 0; sort(line+1,line+temp+1,cmp); sort(yy+1,yy+temp+1); n=temp,t=1,y[1]=yy[1];for (int i=2;i<=temp;++i)if (yy[i]!=yy[i-1]) y[++t]=yy[i];// for (int i=1;i<=t;++i) printf("%d\n",y[i]);//for (int i=1;i<=n;++i) printf("%d\n",line[i].x); return 1;}int main(){ freopen("in.txt","r",stdin); freopen("out.txt","w",stdout);int ans;while(Init()) { Build(1,t);//Debug(1); Insert(1,line[1]); ans=0;for (int i=2;i<=n;++i) { ans+=tree[1].len*(line[i].x-line[i-1].x);//printf("%d\n",ans); Insert(1,line[i]); } printf("%d\n",ans); }return 0;}
转载于:https://www.cnblogs.com/procedure2012/archive/2012/03/17/2403392.html
相关资源：垃圾分类数据集及代码