2 10 10 20 20 15 15 25 25.5 0
Test case #1 Total explored area: 180.00
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=250;
#define lson L,mid,ls
#define rson mid+1,R,rs
int n,m;
int cov[maxn<<2];
double len[maxn<<2],H[maxn];
struct node
{
    double x1,x2,h;
    int v;
    node(double a=0,double b=0,double c=0,int d=0):x1(a),x2(b),h(c),v(d){}
} seg[maxn];
bool cmp(node a,node b)
{
    return a.h<b.h;
}
void init()
{
    sort(H,H+m);
    m=unique(H,H+m)-H;
}
int Hash(double x)
{
    return lower_bound(H,H+m,x)-H;
}
void PushUp(int L,int R,int rt)
{
    if(cov[rt])//有标记肯定整块覆盖了
        len[rt]=H[R+1]-H[L];
    else if(L==R)//没有左右儿子了。
        len[rt]=0;
    else//没有整块覆盖但是被部分覆盖了
        len[rt]=len[rt<<1]+len[rt<<1|1];
}
void update(int L,int R,int rt,int l,int r,int d)
{
    if(l<=L&&R<=r)
    {
        cov[rt]+=d;
        PushUp(L,R,rt);
        return;
    }//这种标记是不用下传的。因为没删除一个上边。一定有一个下边与之对应。
    int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;
    if(l<=mid)
        update(lson,l,r,d);
    if(r>mid)
        update(rson,l,r,d);
    PushUp(L,R,rt);
}
int main()
{
    int cas=1,i,ptr;
    double x1,x2,y1,y2,ans;
    while(scanf("%d",&n),n)
    {
        printf("Test case #%d\n",cas++);
        for(i=ptr=0;i<n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            H[ptr]=x1;
            seg[ptr++]=node(x1,x2,y1,1);
            H[ptr]=x2;
            seg[ptr++]=node(x1,x2,y2,-1);
        }
        m=ptr,ans=0;
        init();
        sort(seg,seg+ptr,cmp);
        memset(len,0,sizeof len);
        memset(cov,0,sizeof cov);
        for(i=0,ptr--;i<ptr;i++)
        {
            update(0,m-1,1,Hash(seg[i].x1),Hash(seg[i].x2)-1,seg[i].v);//m个结点m-1条线段
            ans+=(seg[i+1].h-seg[i].h)*len[1];
        }
        printf("Total explored area: %.2lf\n\n",ans);
    }
    return 0;
}
hdu 1542 Atlantis(线段树&扫描线&面积并),布布扣,bubuko.com
hdu 1542 Atlantis(线段树&扫描线&面积并)
原文:http://blog.csdn.net/bossup/article/details/36191887