题目链接：
HDU 1542 Atlantis
//1628K 0MS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <climits>
#include <algorithm>
#define lson(x) (x<<1)
#define rson(x) ((x<<1)|1)
using namespace std;const int maxn=110;int n,cases=0;
double x1,x2,yy1,y2,xx[maxn<<2];struct SegTree{int left,right,flag;//只有flag=1时该区间才会完全是有效长度double len;
}segtree[maxn<<4];struct Line{int flag;double x1,x2,y;bool operator < (const Line a) const{return y<a.y;}//将横边按所在y值从小到大排序
}line[maxn<<2];void build(int left,int right,int cur)
{segtree[cur].left=left;segtree[cur].right=right;segtree[cur].flag=0;segtree[cur].len=0;//len是区间所存的有效横边长度if(left+1==right) return;int mid=(left+right)>>1;build(left,mid,lson(cur));build(mid,right,rson(cur));//如果是按照[left,mid],[mid+1,right]建树，那么会有一段横坐标[mid,mid+1]丢失
}void calc_len(int cur)
{int flag=segtree[cur].flag;int left=segtree[cur].left;int right=segtree[cur].right;if(flag) segtree[cur].len=xx[right]-xx[left];//整个区间长度是区间左右端点所代表的横坐标之差else if(left+1==right) segtree[cur].len=0;//叶子结点且flag<=0else segtree[cur].len=segtree[lson(cur)].len+segtree[rson(cur)].len;
}void update(int a,int b,int flag,int cur)
{int left=segtree[cur].left;int right=segtree[cur].right;if(left==a&&right==b){segtree[cur].flag+=flag;calc_len(cur);return;}int mid=(left+right)>>1;if(b<=mid) update(a,b,flag,lson(cur));else if(a>=mid){update(a,b,flag,rson(cur));}else {int mid=(left+right)>>1;update(a,mid,flag,lson(cur));update(mid,b,flag,rson(cur));}calc_len(cur);
}int main()
{
#ifdef LOCALfreopen("in.txt","r",stdin);
#endifwhile((~scanf("%d",&n))&&n){int tot=0;for(int i=0;i<n;i++){scanf("%lf %lf %lf %lf",&x1,&yy1,&x2,&y2);xx[tot]=x1,xx[tot+1]=x2;line[tot].x1=x1,line[tot].x2=x2,line[tot].y=yy1,line[tot].flag=1;line[tot+1].x1=x1,line[tot+1].x2=x2,line[tot+1].y=y2,line[tot+1].flag=-1;tot+=2;}sort(xx,xx+tot);int m=unique(xx,xx+tot)-xx;//将横坐标去重build(0,m-1,1);double ans=0;sort(line,line+tot);//for(int i=0;i<tot;i++)// printf("%lf %lf %lf\n",line[i].x1,line[i].x2,line[i].y);for(int i=0;i<tot-1;i++){int a=lower_bound(xx,xx+m,line[i].x1)-xx;int b=lower_bound(xx,xx+m,line[i].x2)-xx;update(a,b,line[i].flag,1);ans+=segtree[1].len*(line[i+1].y-line[i].y);}printf("Test case #%d\n",++cases);printf("Total explored area: %.2f\n\n",ans);}return 0;
}