Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 11777 Accepted Submission(s): 4983
【题意】：
给你n个矩形的左下角（x1,y1）,右上角（x2,y2）,让你求n个矩形面积的并
【分析】：见这里
【代码】：
#include<cstdio> #include<cstring> #include<algorithm> #define m(s) memset(s,0,sizeof s) #define lc k<<1 #define rc k<<1|1 using namespace std; const int N=1e5+10; struct node{ double xl,xr,h; int id; bool operator < (const node &a)const{ return h<a.h; } }b[N]; int n,kase,tag[N<<2]; double sum[N<<2],c[N]; void updata(int k,int l,int r){ if(tag[k]) sum[k]=c[r+1]-c[l];//当前区间被线段覆盖 else if(l==r) sum[k]=0;//已经到了叶子结点且没有被覆盖 else sum[k]=sum[lc]+sum[rc];// 没有完全被覆盖,但是还没到叶子结点,从其子区间中获得信息 } void change(int k,int l,int r,int x,int y,int val){ if(x<=l&&r<=y){ tag[k]+=val;updata(k,l,r); return ; } int mid=l+r>>1; if(x<=mid) change(lc,l,mid,x,y,val); if(y>mid) change(rc,mid+1,r,x,y,val); updata(k,l,r); } int main(){ while(~scanf("%d",&n)&&n){ int cnt=0;double ans=0; double x1,x2,y1,y2; m(sum);m(tag); for(int i=1;i<=n;i++){ scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); b[++cnt]=(node){x1,x2,y1,1};c[cnt]=x1; b[++cnt]=(node){x1,x2,y2,-1};c[cnt]=x2; } sort(b+1,b+cnt+1); sort(c+1,c+cnt+1); int t=unique(c+1,c+cnt+1)-(c+1); for(int i=1;i<cnt;i++){ x1=lower_bound(c+1,c+t+1,b[i].xl)-c; x2=lower_bound(c+1,c+t+1,b[i].xr)-c-1; change(1,1,t,x1,x2,b[i].id); ans+=(b[i+1].h-b[i].h)*sum[1]; } printf("Test case #%d\n",++kase); printf("Total explored area: %.2f\n\n",ans); } return 0; } /* 奉送一组数据 输入： 3 10 10 20 20 15 15 25 30 22 8 28 17 输出： Test case #1 Total explored area: 273.00
再送大家一道题：poj 1389
整体思路一模一样，只是一个为整数，一个为实数,输入输出格式不一样。。 */
-------------------------------------
-------------------------------------
poj 1389
#include<cstdio> #include<cstring> #include<algorithm> #define m(s) memset(s,0,sizeof s) #define lc k<<1 #define rc k<<1|1 using namespace std; const int N=1e5+10; struct node{ int xl,xr,h; int id; bool operator < (const node &a)const{ return h<a.h; } }b[N]; int n,kase,tag[N<<2]; int sum[N<<2],c[N]; void updata(int k,int l,int r){ if(tag[k]) sum[k]=c[r+1]-c[l]; else if(l==r) sum[k]=0; else sum[k]=sum[lc]+sum[rc]; } void change(int k,int l,int r,int x,int y,int val){ if(x<=l&&r<=y){ tag[k]+=val;updata(k,l,r); return ; } int mid=l+r>>1; if(x<=mid) change(lc,l,mid,x,y,val); if(y>mid) change(rc,mid+1,r,x,y,val); updata(k,l,r); } int main(){ int x1,x2,y1,y2; while(scanf("%d%d%d%d",&x1,&y1,&x2,&y2),~x1){ int cnt=0,ans=0;m(sum);m(tag); b[++cnt]=(node){x1,x2,y1,1};c[cnt]=x1; b[++cnt]=(node){x1,x2,y2,-1};c[cnt]=x2; while(scanf("%d%d%d%d",&x1,&y1,&x2,&y2),~x1){ b[++cnt]=(node){x1,x2,y1,1};c[cnt]=x1; b[++cnt]=(node){x1,x2,y2,-1};c[cnt]=x2; } sort(b+1,b+cnt+1); sort(c+1,c+cnt+1); int t=unique(c+1,c+cnt+1)-(c+1); for(int i=1;i<cnt;i++){ x1=lower_bound(c+1,c+t+1,b[i].xl)-c; x2=lower_bound(c+1,c+t+1,b[i].xr)-c-1; change(1,1,t,x1,x2,b[i].id); ans+=(b[i+1].h-b[i].h)*sum[1]; } printf("%d\n",ans); } return 0; }
hdu 1542&&poj 1151 Atlantis[线段树+扫描线求矩形面积的并]
原文：http://www.cnblogs.com/shenben/p/6278982.html