HDU 1542 Atlantis

线段树扫描线入门题

扫描线扫描线 一开始看的时候真的是看的我整个人都不好了 全程懵逼状态 自信心严重受损 最后休整了一天再来看它 用纸和笔动手比划了一点时间才终于算是稍微明白了一点 所以我的建议还是大家自己动手比划一下 毕竟实践出真知 网上的那些题解虽然有图 但他们的语言也只有他们自己读得懂 自己动过手之后才知道他整个过程都是这么精妙

据我所知 线段树的扫描线一般只有两个用处 一个是求覆盖的矩形面积 和覆盖的矩形周长

（毕竟我是鶸 还没碰到过其他用法的扫描线

这题 求面积 数据大 需要离散化

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int maxn=4100;
const double eps=1e-6;
int n,len,flag[maxn];
double ans,xx[maxn],sum[maxn];//xx用于离散化     sum记录扫描线边长   并聚合在sum[1]上
struct line
{
    double lx,rx;
    double y;
    int d;
    line(){}
    line(double _lx,double _rx,double _y,int _d)
    {
        lx=_lx,rx=_rx,y=_y,d=_d;
    }
    bool operator <(const line& a) const
    {
        return y<a.y;
    }
}lines[maxn];

int fin(double a)
{
    int l=1,r=len,mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(xx[mid]==a) return mid;
        else if(xx[mid]>a) r=mid-1;
        else l=mid+1;
    }
    return l;
}

void pushup(int id,int le,int ri)//这是最难理解的一步    我就是卡在了这里   之后比划过才知道玄妙
{
    if(flag[id]) sum[id]=xx[ri+1]-xx[le];
    else if(le==ri) sum[id]=0;
    else sum[id]=sum[id<<1]+sum[id<<1|1];
}

void update(int id,int le,int ri,int st,int en,int add)
{
    if(st<=le&&ri<=en)
    {
        flag[id]+=add;
        pushup(id,le,ri);
        return ;
    }
    int mid=(le+ri)>>1;
    if(st<=mid) update(id<<1,le,mid,st,en,add);
    if(en>mid) update(id<<1|1,mid+1,ri,st,en,add);
    pushup(id,le,ri);
}

int main()
{
    double x1,y1,x2,y2;
    int time=0;
    while(scanf("%d",&n),n)
    {
        memset(flag,0,sizeof flag);
        memset(sum,0,sizeof sum);
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            xx[2*i+1]=x1,xx[2*i+2]=x2;
            lines[2*i+1]=line(x1,x2,y1,1);
            lines[2*i+2]=line(x1,x2,y2,-1);
        }
        n*=2,len=1,ans=0;
        sort(xx+1,xx+1+n);
        sort(lines+1,lines+1+n);
        for(int i=2;i<=n;i++) if(xx[i]!=xx[i+1]) xx[++len]=xx[i];//去重
        for(int i=1;i<n;i++)
        {
            int l=fin(lines[i].lx);
            int r=fin(lines[i].rx)-1;
            update(1,1,len,l,r,lines[i].d);
            ans+=sum[1]*(lines[i+1].y-lines[i].y);
        }
        printf("Test case #%d\nTotal explored area: %.2f\n\n",++time,ans);
    }
    return 0;
}