题意：每组给出矩形左上角和右下角坐标，求矩形面积并；
思路:沿水平方向计算面积并；（切成水平条）；
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; const int maxn=500; struct node{ double x; int l,r,t; //t为上下边标志 }f[maxn]; //水平条 int n; double q[maxn],x1[maxn],yy1[maxn],x2[maxn],yy2[maxn]; //q存储排序后的x坐标 struct segment{ int mark; //并区间标志 double len;//并区间长度 }tree[maxn*20];//线段树 int cmp(node a,node b){ return a.x<b.x; } int ins(int k,int l,int r,int lc,int rc,int t){ if(lc<=l&&r<=rc){ //将标志为t的水平条[l,r]插入根为k,区间为[lc,rc]的线段树 tree[k].mark+=t;//若覆盖，则计算并区域标志；否则插入左右子树 } else{ if((l+r)/2>=lc) ins(k*2,l,(l+r)/2,lc,rc,t); if((l+r)/2<rc) ins(k*2+1,(l+r)/2+1,r,lc,rc,t); } //并区间结束，则k节点的区间长度设为左右子区间的长度之和；否则为q中第r个x坐标与第l个x坐标之间的距离 if(tree[k].mark==0) tree[k].len=tree[k*2].len+tree[k*2+1].len; else tree[k].len=q[r+1]-q[l]; return 0; } int main(){ int t=0; while(scanf("%d",&n)!=EOF){ if(n==0) break; double ans=0; for(int i=1;i<=n;i++){ scanf("%lf%lf%lf%lf",&x1[i],&yy1[i],&x2[i],&yy2[i]); if(x1[i]>x2[i]) swap(x1[i],x2[i]); if(yy1[i]>yy2[i]) swap(yy1[i],yy2[i]); q[i*2-2]=x1[i]; q[i*2-1]=x2[i];//存储x坐标 } sort(q,q+n*2); int m=unique(q,q+n*2)-q; for(int i=1;i<=n;i++){ //将矩阵i的上边左右端点在q表的指针、y坐标、上边标志存入f[i*2-2];将矩阵i的下边左右端点在q表的指针、y坐标、下边标志存入f[i*2-1] f[i*2-2].l=lower_bound(q,q+m,x1[i])-q; f[i*2-2].r=lower_bound(q,q+m,x2[i])-q; f[i*2-2].x=yy1[i]; f[i*2-2].t=1; f[i*2-1].l=lower_bound(q,q+m,x1[i])-q; f[i*2-1].r=lower_bound(q,q+m,x2[i])-q; f[i*2-1].x=yy2[i]; f[i*2-1].t=-1; } sort(f,f+n*2,cmp); for(int i=0;i<n*2;i++){ if(i) ans+=tree[1].len*(f[i].x-f[i-1].x); ins(1,0,m,f[i].l,f[i].r-1,f[i].t);//将当前水平条插入线段树 } printf("Test case #%d ",++t); printf("Total explored area: %.2f ",ans); } return 0; }