题目链接：点击打开链接

题目描写叙述：给定一些矩形，求这些矩形的总面积。假设有重叠。仅仅算一次

解题思路：扫描线+线段树+离散（代码从上往下扫描）

代码：

#include<cstdio>

#include <algorithm>

#define MAXN 110

#define LL ((rt<<1)+1)

#define RR ((rt<<1)+2)

using namespace std;

int n;

struct segment{

    double l,r,h;

    int f;

    bool operator<(const segment& b)const{

        return h>b.h;

    }

}sg[2*MAXN];

double pos[2*MAXN];

int id;

void addSegment(double x1,double y1,double x2,double y2){

    sg[id].l=x1;sg[id].r=x2;

    sg[id].h=y1;sg[id].f=1;

    pos[id++]=x1;

    sg[id].l=x1;sg[id].r=x2;

    sg[id].h=y2;sg[id].f=-1;

    pos[id++]=x2;

}

int binary(double key,int low,int high){

    while(low<=high){

        int mid=(low+high)/2;

        if(pos[mid]==key)

            return mid;

        else if(key<pos[mid])

            high=mid-1;

        else

            low=mid+1;

    }

    return -1;

}

struct Tree{

    int l,r;

    int cover;

    double len;

}tree[8*MAXN];

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

    tree[rt].l=l;

    tree[rt].r=r;

    tree[rt].cover=0;

    tree[rt].len=0;

    if(l==r-1)

        return;

    int mid=(l+r)>>1;

    build(LL,l,mid);

    build(RR,mid,r);

}

void pushup(int rt){

    if(tree[rt].cover)

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

    else if(tree[rt].l==tree[rt].r-1)

        tree[rt].len=0;

    else

        tree[rt].len=tree[LL].len+tree[RR].len;

}

void update(int rt,int l,int r,int f){

    if(tree[rt].l==l&&tree[rt].r==r){

        tree[rt].cover+=f;

        pushup(rt);

        return;

    }

    int mid=(tree[rt].l+tree[rt].r)>>1;

    if(r<=mid)

        update(LL,l,r,f);

    else if(l>=mid)

        update(RR,l,r,f);

    else{

        update(LL,l,mid,f);

        update(RR,mid,r,f);

    }

    pushup(rt);

}

int main(){

    int Case=0;

    while(scanf("%d",&n)!=EOF&&n!=0){

        id=0;

        double x1,y1,x2,y2;

        for(int i=0;i<n;++i){

            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);

            addSegment(x1,y1,x2,y2);

        }

        n=(n<<1);

        sort(sg,sg+n);

        sort(pos,pos+n);

        int m=1;

        for(int i=1;i<n;++i)

            if(pos[i]!=pos[i-1])

                pos[m++]=pos[i];

        build(0,0,m-1);

        double ans=0;

        int l=binary(sg[0].l,0,m-1);

        int r=binary(sg[0].r,0,m-1);

        update(0,l,r,sg[0].f);

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

            ans+=(sg[i-1].h-sg[i].h)*tree[0].len;

            l=binary(sg[i].l,0,m-1);

            r=binary(sg[i].r,0,m-1);

            update(0,l,r,sg[i].f);

        }

        printf("Test case #%d\n",++Case);

        printf("Total explored area: %.2f\n\n",ans);

    }

    return 0;

}