POJ 1151

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#define N 405
using namespace std;

int flg[N],sum[4*N],X[N];
int k,u,mid,c,t;

struct node{
    int flag;
    double lx,rx,y;
    node(){}
    node(double a,double b,double c,int d){
        lx=a,rx=b,y=c,flag=d;
    }
    bool operator < (node b)const{
        return y<b.y;
    }
}line[N];

void push_up(int u,int l,int r){
	if(flg[u])
		sum[u]=X[r+1]-X[l];
	else
		if(l==r)
			sum[u]=0;
		else sum[u]=sum[u<<1]+sum[u<<1+1];
}

void updat(int u,int l,int r,int tl,int tr,int c){
	if(tl<=l&&r<=tr){
		flg[u]+=c;
		push_up(u,l,r);
		return;
	}
	int mid=(l+r)>>1;
	updat(u<<1,l,mid,tl,tr,c);
	updat(u<<1+1,mid,r,tl,tr,c);
	push_up(u,l,r);
}

int main(){
	int n,a,b,i;
	int cnt=1;
	while(scanf("%d",&n)&&n){
		int num=0;
		memset(sum,0,sizeof(sum));
		memset(flg,0,sizeof(flg));
		double x1,x2,y1,y2;
		for(i=0;i<n;i++){
			scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
			num++,line[num]=node(x1,x2,y1,1),X[num]=x1;
			num++,line[num]=node(x1,x2,y2,-1),X[num]=x2;
		}
		sort(line+1,line+num+1);
		sort(X+1,X+1+num);
		double ans=0;
		for(i=0;i<num;i++){
			int l=lower_bound(X+1,X+1+num,line[i].lx)-X;
			int r=lower_bound(X+1,X+1+num,line[i].rx)-X-1;
			updat(1,1,num,l,r,line[i].flag);
			ans+=sum[1]*(line[i+1].y-line[i].y);
		}
		printf("Test case #%d\n",cnt++);
    	printf("Total explored area: %.2lf\n\n",ans);
	}
	return 0;
}