POJ1151+线段树+扫描线

/*
线段树+扫描线+离散化
求多个矩形的面积
*/
#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 = 105;
const int maxm = 210;
struct SegTree{
	int l,r;
	int cover;
	double L_val,R_val;
	double sum;
}ST[ maxm<<2 ];
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 = 0;
	ST[ n ].sum = 0;
	ST[ n ].L_val = yIndex[ L ];
	ST[ n ].R_val = yIndex[ R ];
	if( R-L>1 ){
		int mid = (L+R)/2;
		build( L,mid,2*n );
		build( mid,R,2*n+1 );
	}
}
void PushUp( int n ){
	if( ST[ n ].cover>0 ){
		ST[ n ].sum = ST[ n ].R_val-ST[ n ].L_val;
	}
	else if( ST[ n ].r-ST[ n ].l>1 ){
		ST[ n ].sum = ST[ 2*n ].sum+ST[ 2*n+1 ].sum;
	}
	else
		ST[ n ].sum = 0;
}
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)/2;
		if( mid>=right ) update( left,right,InOut,2*n );
		else if( mid<=left ) update( left,right,InOut,2*n+1 );
		else {
			update( left,mid,InOut,2*n );
			update( mid,right,InOut,2*n+1 );
		}
	}
	PushUp( n );
}

int main(){
	int n;
	int T = 1;
	while( scanf("%d",&n)==1,n ){
		printf("Test case #%d\n",T++);
		double x1,y1,x2,y2;
		int cnt = 0;
		for( int i=0;i<n;i++ ){
			scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
			yLine[ 2*i ].x = x1;
			yLine[ 2*i+1 ].x = x2;
			yLine[ 2*i ].y1 = yLine[ 2*i+1 ].y1 = y1;
			yLine[ 2*i ].y2 = yLine[ 2*i+1 ].y2 = y2;
			yLine[ 2*i ].InOut = true;
			yLine[ 2*i+1 ].InOut = false;
			yIndex[ 2*i ] = y1;
			yIndex[ 2*i+1 ] = y2;
		}
		sort( yLine,yLine+2*n,cmp );
		sort( yIndex,yIndex+2*n );
		for( int i=1;i<2*n;i++ ){
			if( yIndex[i]!=yIndex[i-1] )
				yIndex[ cnt++ ] = yIndex[ i-1 ];
		}
		yIndex[ cnt++ ] = yIndex[ 2*n-1 ];
		build( 0,cnt-1,1 );
		double res = 0;
		update( GetIndex( yLine[0].y1,cnt ),GetIndex( yLine[0].y2,cnt ),yLine[0].InOut,1 );
		for( int i=1;i<2*n;i++ ){
			res += ST[ 1 ].sum*( yLine[i].x-yLine[i-1].x );
			update( GetIndex( yLine[i].y1,cnt ),GetIndex( yLine[i].y2,cnt ),yLine[i].InOut,1 );
		}
		printf("Total explored area: %.2lf\n\n",res);
	}
	return 0;
}