1 //13435314    ooyyloo    1151    Accepted    748K    0MS    G++    2079B    2014-09-12 16:16:35  2 #include <cstdio>  3 #include <algorithm>  4 #include <iostream>  5 #include <set>  6 #define mp make_pair  7 #define dbg(x) cout<<#x<<"="<<x<<endl  8 #define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)  9 using namespace std; 10 const int maxn=201; 11  12 struct line{ 13     double x,y1,y2; 14     int v; 15     bool operator< (const line &a) const { return x<a.x; } 16 }wu[maxn]; 17  18 int n,nn; 19 double ans; 20 set<double> sety; 21 double hashy[maxn]; int hpo; 22  23 //seg tree 24 double sh[maxn<<2]; int cov[maxn<<2]; 25 void build(int k,int l,int r) 26 { 27     sh[k]=cov[k]=0; 28     if (l+1==r) return; 29     int mid=l+r>>1; 30     build(k<<1,l,mid); 31     build(k<<1|1,mid,r); 32 } 33 void update(int k,int l,int r) 34 { 35     if (cov[k])      sh[k]=hashy[r]-hashy[l]; 36     else if (l+1==r) sh[k]=cov[k]?hashy[r]-hashy[l]:0; 37     else              sh[k]=sh[k<<1]+sh[k<<1|1]; 38 } 39 void modify(int k,int l,int r,int ll,int rr,int v)//we just care about father 40 { 41     if (l>=ll&&r<=rr) 42     { 43         cov[k]+=v; 44         update(k,l,r); 45         return; 46     } 47     int mid=l+r>>1; 48     if (ll<mid) modify(k<<1,l,mid,ll,rr,v); 49     if (rr>mid) modify(k<<1|1,mid,r,ll,rr,v); 50     update(k,l,r); 51 } 52  53  54 void init() 55 { 56     nn=n<<1; 57     sety.clear(); 58  59     double x1,y1,x2,y2; 60     for (int i=1;i<=n;i++) 61     { 62         scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); 63         wu[i].x=x1; wu[i].y1=y1; wu[i].y2=y2; wu[i].v=1; 64         wu[i+n].x=x2; wu[i+n].y1=y1; wu[i+n].y2=y2; wu[i+n].v=-1; 65         sety.insert(y1); sety.insert(y2); 66     } 67     hpo=0; 68     foreach(it,sety) hashy[++hpo]=*it; 69     //for (auto x:sety) hashy[++hpo]=x; 70 } 71 int bs(double d) 72 { 73     int l=1,r=hpo,mid; 74     while (l<=r) 75     { 76         mid=l+r>>1; 77         if (d>hashy[mid]) l=mid+1; 78         else               r=mid-1; 79     } 80     return l; 81 } 82 void solve() 83 { 84     ans=0.0; 85     sort(wu+1,wu+1+nn); 86     modify(1,1,hpo,bs(wu[1].y1),bs(wu[1].y2),wu[1].v); 87     for (int z=2;z<=nn;z++) 88     { 89         ans+=sh[1]*(wu[z].x-wu[z-1].x); 90         modify(1,1,hpo,bs(wu[z].y1),bs(wu[z].y2),wu[z].v); 91     } 92 } 93 int main() 94 { 95     for (int tt=1;scanf("%d",&n)!=EOF;tt++) 96     { 97         if (!n) break; 98         init(); 99         build(1,1,hpo);100         solve();101         printf("Test case #%d\n",tt);102         printf("Total explored area: %.2f\n",ans);103         puts("");104     }105     return 0;106 }