poj1151 Atlantis——扫描线+线段树

经典的扫描线问题；

可以用线段树的每个点代表横向被矩形上下边分割开的每一格，这样将一个矩形的出现或消失化为线段树上的单点修改；

每个格子记录两个值：c(矩形存在情况)，sum(对当前答案作出贡献的长度)；

将y离散化作为建树的依据；

一开始没想到线段树上的点应该是横向的格子，写了个乱七八糟：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int t,n,xt;

double s[],ans,tr[],mx,eps=0.36;

struct P{

    double x,y1,y2;

    int tp;

    P(int x=,int y1=,int y2=,int t=):x(x),y1(y1),y2(y2),tp(t) {}

}p[];

void pushup(int x)

{

    tr[x]=tr[x<<]+tr[x<<|];

}

void add(int x,double l,double r,double L,double R,int w)

{

//    cout<<x<<endl;

//    printf("l=%lf r=%lf eps=%lf\n",l,r,eps);

    if(r-l<eps)

    {

        s[x]+=w;

        if(s[x])tr[x]=;

        else tr[x]=;

//        printf("s[%d]=%d\n",x,s[x]);

        return;

    }

    double mid=(l+r)/;

    if(mid>=L)add(x<<,l,mid,L,R,w);

    if(mid<R)add(x<<|,mid+,r,L,R,w);

    pushup(x);

}

bool cmp(P x,P y){return x.x<y.x;}

int main()

{

    while(scanf("%d",&n)==)

    {

        t++;xt=;mx=;ans=;

        memset(tr,,sizeof tr);

        memset(s,,sizeof s);

        if(!n)return ;

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

        {

            xt++;scanf("%lf%lf",&p[xt].x,&p[xt].y1);

            xt++;scanf("%lf%lf",&p[xt].x,&p[xt].y1);

            p[xt-].y2=p[xt].y1;p[xt].y2=p[xt-].y1;

            p[xt-].tp=;p[xt].tp=-;

            mx=max(mx,max(p[xt].y1,p[xt].y2));

        }

        sort(p+,p+xt+,cmp);

        double lst=-;

        for(int i=;i<=xt;i++)

        {

            if(p[i].y1>p[i].y2)swap(p[i].y1,p[i].y2);

            add(,,mx,p[i].y1,p[i].y2,p[i].tp);

            if(lst!=-)ans+=(p[i].x-lst)*tr[];

            lst=p[i].x;

        }

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

    }

    return ;

}

囧

然后参考别人的博客，努力理解了半天，模仿着打了出来，终于A了...

学到了add()函数里面那种二分的方法。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,ct,t;

double ans,y[];

struct P{

    int l,r,c;//c为上下矩形抵消数

    double ly,ry,sum;//sum为此时计入计算的长度

}tr[];

struct E{

    int tp;

    double x,ly,ry;

}ed[];

bool cmp(E x,E y){return x.x<y.x;}

void build(int x,int l,int r)

{

    tr[x].l=l;tr[x].r=r;

    tr[x].ly=y[l];tr[x].ry=y[r];

    tr[x].c=;tr[x].sum=;

    if(l==r-)return;

    int mid=(l+r)>>;

    build(x<<,l,mid);

    build(x<<|,mid,r);//不是mid+1，因为l,r表示此块上下两边

}

void pushup(int x)

{

    if(tr[x].c>)//全选

        tr[x].sum=tr[x].ry-tr[x].ly;

    else if(tr[x].l==tr[x].r-)//仅有一格且被退出

         tr[x].sum=;

    else//可能有其他边覆盖

        tr[x].sum=tr[x<<].sum+tr[x<<|].sum;

}

void add(int x,E e)

{

    if(tr[x].ly==e.ly&&tr[x].ry==e.ry)

    {

        tr[x].c+=e.tp;

        pushup(x);

        return;

    }

    if(tr[x<<].ry>=e.ry)add(x<<,e);

    else if(tr[x<<|].ly<=e.ly)add(x<<|,e);

    else

    {

        E tmp=e;

        tmp.ry=tr[x<<].ry;

        add(x<<,tmp);

        tmp=e;

        tmp.ly=tr[x<<|].ly;

        add(x<<|,tmp);

    }

    pushup(x);

}

int main()

{

    while(scanf("%d",&n)==)

    {

        t++;

        if(!n)return ;

        ct=;ans=;

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

        {

            double x1,y1,x2,y2;

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

            y[++ct]=y1;ed[ct].tp=;

            ed[ct].x=x1;ed[ct].ly=y1;ed[ct].ry=y2;

            y[++ct]=y2;ed[ct].tp=-;

            ed[ct].x=x2;ed[ct].ly=y1;ed[ct].ry=y2;

        }

        sort(ed+,ed+ct+,cmp);

        sort(y+,y+ct+);

        build(,,ct);

        add(,ed[]);

        for(int i=;i<=ct;i++)

        {

            ans+=tr[].sum*(ed[i].x-ed[i-].x);

            add(,ed[i]);//上下勿反

        }

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

    }

    return ;

}

秒客网

poj1151 Atlantis——扫描线+线段树

相关文章