题意：求矩形面积的并

思路：

注意是[l,mid][mid,r] 这是真正的线段了

就当扫描线模板使吧~

//By SiriusRen

#include <cmath>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define eps 1e-5

int N,tot,n,cases;

double y[666],ans=0;

struct Node{double x,y1,y2;int cover;}node[666];

struct Tree{double l,r,len;int cover;}tree[66666];

bool cmp(Node a,Node b){return a.x<b.x;}

void build(int l,int r,int pos){

    tree[pos].l=y[l],tree[pos].r=y[r],tree[pos].len=tree[pos].cover=0;

    if(l+1==r)return;

    int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;

    build(l,mid,lson),build(mid,r,rson);

}

void push_up(int l,int r,int pos){

    if(tree[pos].cover>0)

        tree[pos].len=tree[pos].r-tree[pos].l;

    else if(l+1==r)tree[pos].len=0;

    else tree[pos].len=tree[pos<<1].len+tree[pos<<1|1].len;

}

void update(int l,int r,int pos,Node jy){

    if(tree[pos].l>=jy.y1&&tree[pos].r<=jy.y2){

        tree[pos].cover+=jy.cover;push_up(l,r,pos);

        return;

    }

    int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;

    if(tree[lson].r>=jy.y2)update(l,mid,lson,jy);

    else if(tree[rson].l<=jy.y1)update(mid,r,rson,jy);

    else update(l,mid,lson,jy),update(mid,r,rson,jy);

    push_up(l,r,pos);

}

int main(){

    while(scanf("%d",&N)&&N){

        ans=tot=0;

        for(int i=1;i<=N;i++){

            double X1,Y1,X2,Y2;

            scanf("%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2);

            node[++tot].x=X1,node[tot].y1=Y1,node[tot].y2=Y2;node[tot].cover=1;y[tot]=Y1;

            node[++tot].x=X2,node[tot].y1=Y1,node[tot].y2=Y2;node[tot].cover=-1;y[tot]=Y2;

        }

        sort(node+1,node+1+tot,cmp),sort(y+1,y+1+tot);

        n=unique(y+1,y+1+tot)-y-1;

        build(1,n,1),update(1,n,1,node[1]);

        for(int i=2;i<=tot;i++){

            ans+=tree[1].len*(node[i].x-node[i-1].x);

            update(1,n,1,node[i]);

        }

        printf("Test case #%d\nTotal explored area: %.2lf\n\n",++cases,ans);

    }

}