hdu 1542 矩形面积并
线段树扫描线。。
思路：将每个矩形看成平行于y轴的两条线段，第一条位置 x1，第二条位置 x2，两条线段的端点均为 y1，y2 （注：x1，y1 为矩形左下角坐标，x2，y2为右上角坐标，题目描述错了） ，然后将左边的 线段标记cover=1，右边的线段 标记cover=-1，线段树记录 len 表示 当前该区间可用于与下一线段求并面积的y坐标区间长度。
按x坐标排序后从左到右扫描，同时要注意数据离散化。。
样例分析：第一条线段插入以后，T[1].len=10；就是说这条线段可以和下一条线段构成面积的长度是 10，那么就是 10*（第二条线段x坐标-第一条线段x坐标）即 10*（15-10）=50.
第二条插入后 T[1].len=15.5；可得到的面积 为 15.5*（20-15）=77.5
第三条插入以后 T[1].len=10.5 可得到的面积 为 10.5*（25-20）=52.5
所以 总得到的面积 为 180
#include<iostream>#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;#define lson u<<1#define rson u<<1|1#define MAXN 500double ycoord[MAXN];//ycoord..struct SEG{ double ly,hy,x;//low y..high y..x.. int cover; SEG(){} SEG(double a,double b,double c,int d):ly(a),hy(b),x(c),cover(d){}bool operator < (const SEG& cmp)const{return x<cmp.x;}}seg[MAXN];struct Node{ int lef,rig; double len;//该区间可用于与下一线段求并面积的y坐标区间长度.. int cover;}T[MAXN<<2];void Build(int u,int l,int r){ T[u].lef=l; T[u].rig=r; T[u].cover=0; T[u].len=0; if(l+1==r)return; int mid=(l+r)>>1; Build(lson,l,mid); Build(rson,mid,r);}void PushUp(int u){ if(T[u].cover>0)T[u].len=ycoord[T[u].rig]-ycoord[T[u].lef]; else if(T[u].lef+1==T[u].rig)T[u].len=0; else T[u].len=T[lson].len+T[rson].len;}void Update(int u,int l,int r,int cover){if(r<T[u].lef||T[u].rig<l)return; if(l<=T[u].lef&&T[u].rig<=r){ T[u].cover+=cover; } else { if(l<=T[lson].rig)Update(lson,l,r,cover); if(r>=T[rson].lef)Update(rson,l,r,cover); }PushUp(u);}int main(){ int n; int cas=0; while(scanf("%d",&n)&&n){ double x1,y1,x2,y2; int cnt=0; for(int i=0;i<n;i++){ scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); ycoord[cnt]=y1; seg[cnt++]=SEG(y1,y2,x1,1); ycoord[cnt]=y2; seg[cnt++]=SEG(y1,y2,x2,-1); } sort(ycoord,ycoord+cnt); sort(seg,seg+cnt);int num=unique(ycoord,ycoord+cnt)-ycoord; Build(1,0,num-1); double sumarea=0; for(int i=0;i<cnt-1;i++){ int ll=lower_bound(ycoord,ycoord+num,seg[i].ly)-ycoord; int rr=lower_bound(ycoord,ycoord+num,seg[i].hy)-ycoord; Update(1,ll,rr,seg[i].cover); sumarea+=T[1].len*(seg[i+1].x-seg[i].x); }printf("Test case #%d\n",++cas); printf("Total explored area: %.2lf\n\n",sumarea); }}