/*
线段树+扫描线+离散化
求多个矩形的面积
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<math.h>
#include<map>
using namespace std;
const int maxn = ;
const int maxm = ;
struct SegTree{
int l,r;
int cover;
double L_val,R_val;
double sum;
}ST[ maxm<< ];
struct Line{
double x,y1,y2;
bool InOut;
}yLine[ maxm ];
int cmp( Line a,Line b ){
return a.x<b.x;
}
double yIndex[ maxm ];
int GetIndex( double val,int cnt ){
return lower_bound( yIndex,yIndex+cnt,val )-yIndex;
} void build( int L,int R,int n ){
ST[ n ].l = L;
ST[ n ].r = R;
ST[ n ].cover = ;
ST[ n ].sum = ;
ST[ n ].L_val = yIndex[ L ];
ST[ n ].R_val = yIndex[ R ];
if( R-L> ){
int mid = (L+R)/;
build( L,mid,*n );
build( mid,R,*n+ );
}
}
void PushUp( int n ){
if( ST[ n ].cover> ){
ST[ n ].sum = ST[ n ].R_val-ST[ n ].L_val;
}
else if( ST[ n ].r-ST[ n ].l> ){
ST[ n ].sum = ST[ *n ].sum+ST[ *n+ ].sum;
}
else
ST[ n ].sum = ;
}
void update( int left,int right,bool InOut,int n ){
if( left==ST[ n ].l&&right==ST[ n ].r ){
if( InOut==true ){
ST[ n ].cover++;
}
else{
ST[ n ].cover--;
}
}
else {
int mid = (ST[ n ].l+ST[ n ].r)/;
if( mid>=right ) update( left,right,InOut,*n );
else if( mid<=left ) update( left,right,InOut,*n+ );
else {
update( left,mid,InOut,*n );
update( mid,right,InOut,*n+ );
}
}
PushUp( n );
} int main(){
int n;
int T = ;
while( scanf("%d",&n)==,n ){
printf("Test case #%d\n",T++);
double x1,y1,x2,y2;
int cnt = ;
for( int i=;i<n;i++ ){
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
yLine[ *i ].x = x1;
yLine[ *i+ ].x = x2;
yLine[ *i ].y1 = yLine[ *i+ ].y1 = y1;
yLine[ *i ].y2 = yLine[ *i+ ].y2 = y2;
yLine[ *i ].InOut = true;
yLine[ *i+ ].InOut = false;
yIndex[ *i ] = y1;
yIndex[ *i+ ] = y2;
}
sort( yLine,yLine+*n,cmp );
sort( yIndex,yIndex+*n );
for( int i=;i<*n;i++ ){
if( yIndex[i]!=yIndex[i-] )
yIndex[ cnt++ ] = yIndex[ i- ];
}
yIndex[ cnt++ ] = yIndex[ *n- ];
build( ,cnt-, );
double res = ;
update( GetIndex( yLine[].y1,cnt ),GetIndex( yLine[].y2,cnt ),yLine[].InOut, );
for( int i=;i<*n;i++ ){
res += ST[ ].sum*( yLine[i].x-yLine[i-].x );
update( GetIndex( yLine[i].y1,cnt ),GetIndex( yLine[i].y2,cnt ),yLine[i].InOut, );
}
printf("Total explored area: %.2lf\n\n",res);
}
return ;
}
04-30 21:13