hdu 1542矩形面積及び

線分ツリーの走査線.
構想:各矩形をy軸に平行な2本の線分と見なし、1本目の位置x 1、2本目の位置x 2、2本目の線分の端点はy 1、y 2(注:x 1、y 1は矩形左下角座標、x 2、y 2は右上角座標、タイトル記述が間違っている)で、左の線分をcover=1、右の線分をcover=1と表記し、セグメントツリーレコードlenは、現在この区間が次のセグメントと面積を加算するために使用できるy座標区間の長さを示す.
x座標で並べ替えて左から右にスキャンし、データの離散化に注意します.
サンプル分析:最初の線分を挿入した後、T[1].len=10;すなわち、この線分と次の線分との構成面積の長いが10である、10*(第2線分x座標-第1線分x座標)である10*(15-10)=50である.
第2条挿入後T[1]len=15.5;得られる面積は15.5*(20-15)=77.5
第3条挿入後T[1].len=0.5得られる面積は10.5*(25-20)=52.5
だから総得られた面積は180です

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

#define lson u<<1
#define rson u<<1|1
#define MAXN 500

double ycoord[MAXN];//ycoord..

struct SEG{
    double ly,hy,x;//low y..high y..x..
    int cover;
    SEG(){}
    SEG(double a,double b,double c,int d):ly(a),hy(b),x(c),cover(d){}
	bool operator < (const SEG& cmp)const{
		return x<cmp.x;
	}
}seg[MAXN];

struct Node{
    int lef,rig;
    double len;//                y      ..
    int cover;
}T[MAXN<<2];

void Build(int u,int l,int r){
    T[u].lef=l;
    T[u].rig=r;
    T[u].cover=0;
    T[u].len=0;
    if(l+1==r)return;
    int mid=(l+r)>>1;
    Build(lson,l,mid);
    Build(rson,mid,r);
}

void PushUp(int u){
    if(T[u].cover>0)T[u].len=ycoord[T[u].rig]-ycoord[T[u].lef];
    else if(T[u].lef+1==T[u].rig)T[u].len=0;
    else T[u].len=T[lson].len+T[rson].len;
}

void Update(int u,int l,int r,int cover){
	if(r<T[u].lef||T[u].rig<l)return;
    if(l<=T[u].lef&&T[u].rig<=r){
        T[u].cover+=cover;
    }
    else {
        if(l<=T[lson].rig)Update(lson,l,r,cover);
        if(r>=T[rson].lef)Update(rson,l,r,cover);
    }
	PushUp(u);
}

int main(){
    int n;
    int cas=0;
    while(scanf("%d",&n)&&n){
        double x1,y1,x2,y2;
        int cnt=0;
        for(int i=0;i<n;i++){
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            ycoord[cnt]=y1;
            seg[cnt++]=SEG(y1,y2,x1,1);
            ycoord[cnt]=y2;
            seg[cnt++]=SEG(y1,y2,x2,-1);
        }
        sort(ycoord,ycoord+cnt);
        sort(seg,seg+cnt);
		int num=unique(ycoord,ycoord+cnt)-ycoord;
        Build(1,0,num-1);
        double sumarea=0;
        for(int i=0;i<cnt-1;i++){
        	int ll=lower_bound(ycoord,ycoord+num,seg[i].ly)-ycoord;
        	int rr=lower_bound(ycoord,ycoord+num,seg[i].hy)-ycoord;
        	Update(1,ll,rr,seg[i].cover);
        	sumarea+=T[1].len*(seg[i+1].x-seg[i].x);
        }
		printf("Test case #%d
",++cas);
        printf("Total explored area: %.2lf

",sumarea);
    }
}