#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstdlib> using namespace std; #define M 1010 typedef int I; typedef double D; typedef struct { D x; D y_down; D y_up; I cover; } node;//定义线段,每一个都存一个x并且cover标记是左边的还是右边的,y_down和y_up表示这一线段对应y的坐标 node L[3*M]; typedef struct tr { I l,r; I cover; D len; } tree;//定义树的结构,cover表示这条边有没有被覆盖过,len表示这一段区间的y轴的长度 tree t[3*M]; D yy[M];//对y坐标进行离散用 I cmp(node a,node b) { return a.x < b.x; } void build(I id,I l,I r) { t[id].cover=0; t[id].l=l; t[id].len=0; t[id].r=r; if(l+1==r) return ; I mid=(l+r)>>1; build(id<<1,l,mid); build(id<<1|1,mid,r); } void fun(I id) { if(t[id].cover)//如果被覆盖则此段的长度len为对应y坐标之差 t[id].len=yy[t[id].r]-yy[t[id].l]; else if(t[id].l+1==t[id].r)//若为叶子节点,长度len为0 t[id].len=0; else//若没有被覆盖过,并且不是叶子节点,则此段的长度为下面分支对应长度之和 t[id].len=t[id<<1].len+t[id<<1|1].len; } void update(I id,I l,I r,I v) { if(t[id].l>=r || t[id].r<=l)//如果没有在这个距离内,直接返回,不用再向下搜了 return ; if(t[id].l<=l && t[id].r<=r)//若此段包含着,则说明,被覆盖 { t[id].cover+=v; fun(id);//差找此段的长度len return ; } update(id<<1,l,r,v);//如果以上都不满足则继续向下搜 update(id<<1|1,l,r,v); fun(id);//最后还要搜一下长度 } I find(I l,I r,D x)//二分查找,对y坐标进行离散化 { while(l<=r) { I mid=(l+r)>>1; if(fabs(yy[mid]-x)<1e-10) return mid; else if(yy[mid]>x) r=mid-1; else l=mid+1; } return l; } I main() { I n,i,ca; ca=1; while(scanf("%d",&n),n) { I m; m=0; for(i=0; i<n; i++) { D x1,x2,y1,y2; scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); yy[m]=y1; //把坐标定点记录成线段,每条线段保存的信息有,线段的定点,还有在这个句型中的位置,左边还是右边 L[m].cover=1; L[m].x=x1; L[m].y_down=y1; L[m].y_up=y2; m++; yy[m]=y2; L[m].cover=-1; L[m].x=x2; L[m].y_down=y1; L[m].y_up=y2; m++; } I len=1; sort(yy,yy+m);//对y进行升序排序 for(i=1; i<m; i++)//去重 { if(yy[i-1]!=yy[i]) yy[len++]=yy[i]; } len--; build(1,0,len);//建树,以离散后y坐标为区间建树 sort(L,L+m,cmp); D ans=0; for(i=0; i<m-1; i++) { I a,b; a=find(0,len,L[i].y_down); b=find(0,len,L[i].y_up); update(1,a,b,L[i].cover);//更新对应区间 ans+=t[1].len*(L[i+1].x-L[i].x);//累加求此段被分割的面积 } //输出 printf("Test case #%d\n",ca++); printf("Total explored area: %.2f\n",ans); } return 0; }