题意：求n个矩阵的面积并。
/* 线段树维护扫描线 把每个矩形看成两条线段，从左到右添加线段，如果是矩形左边的线段，那就给线段所在的区间（y值）cover+1，反之则cover-1。 并且如果这条线段添加之前它所在的区间的cover>0，则统计面积。 另外如果求面积的交集，线段所在的区间的cover>1时统计面积。 PS:个人认为某位大神写的博客很好理解（这位大神还搞了一个线段树专辑？%%%）： http://www.cnblogs.com/ka200812/archive/2011/11/13/2247064.html 但是我觉得第一种算法每次都要找到叶子节点，貌似有点浪费时间，然而第二种又不会。。。 */ #include<cstdio> #include<iostream> #include<algorithm> #define N 110 using namespace std; double y[N*2];int n,cnt,Cas; struct node{ double x,y_down,y_up;int flag; bool operator < (const node &s1)const{ return x<s1.x; } };node e[N*2]; struct Node{ double x,y_down,y_up;int cover; int flag;//是否为叶子节点 };Node tree[1000*N]; void build(int k,int l,int r){ tree[k].cover=0; tree[k].x=-1;//代表这个区间最近一次的横坐标 tree[k].y_down=y[l]; tree[k].y_up=y[r]; tree[k].flag=0; if(l+1==r){ tree[k].flag=1; return; } int mid=l+r>>1; build(k*2,l,mid); build(k*2+1,mid,r); } double insert(int k,double x,double l,double r,int flag){ if(r<=tree[k].y_down||l>=tree[k].y_up) return 0; if(tree[k].flag){ if(tree[k].cover>0){ double ans=(x-tree[k].x)*(tree[k].y_up-tree[k].y_down); tree[k].cover+=flag; tree[k].x=x; return ans; } else { tree[k].cover+=flag; tree[k].x=x; return 0; } } double ans=0; ans+=insert(k*2,x,l,r,flag); ans+=insert(k*2+1,x,l,r,flag); return ans; } int main(){ while(scanf("%d",&n)){ if(!n) break; cnt=0; for(int i=1;i<=n;i++){ double x1,y1,x2,y2; scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); y[++cnt]=y1; e[cnt].x=x1; e[cnt].y_down=y1; e[cnt].y_up=y2; e[cnt].flag=1; y[++cnt]=y2; e[cnt].x=x2; e[cnt].y_down=y1; e[cnt].y_up=y2; e[cnt].flag=-1; } sort(y+1,y+cnt+1);//写成了sort(y,y+cnt+1)，1WA sort(e+1,e+cnt+1); build(1,1,cnt); double ans=0; for(int i=1;i<=cnt;i++){ ans+=insert(1,e[i].x,e[i].y_down,e[i].y_up,e[i].flag); } printf("Test case #%d Total explored area: %.2f ",++Cas,ans); } return 0; }