学习笔记——扫描线

忘是亡心i 2023-06-05 12:44 8阅读 0赞

扫描线的主要步骤就是先对于一个维度进行排序扫描，并用一些数据结构维护当前扫描线所产生的贡献。（一般是用离散化+线段树）

今天就用平面上的矩阵的周长并和面积并来讲一讲扫描线。

[POJ1151——Atlantis][POJ1151_Atlantis]（矩阵面积并）

我们考虑对于$y$轴从下至上扫描，每次看剩下的底边再乘上此次更新的高度，这样就可以

我们先按照$y$轴进行排序，然后对于$x$轴进行离散化，用线段树$cnt$保存这段区间内被完全覆盖了几次，$sum$保存这个区间内剩下底边的长度。

在扫描时，我们分类当前边是上位边还是下位边，若是上位边就对剩下区间进行覆盖，下位边则进行删除（即反着更新），然后从第二条扫描线开始统计答案即可

注：在代码实现方面，其实区间修改并没必要写$pushdown$函数，因为查询永远查的是$sum\[1\]$，而修改操作也一定是成对出现，并不需要把上面的信息处理到下面。

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    typedef long long ll;
    const double inf=2e9;
    const int N=102000;
    
    int n;
    struct Point{
        double x1,y1,x2,y2;
    }a[N];
    
    struct Line{
        double y;
        int flag,id;//flag=1:下位边  flag=-1:上位边 
        bool operator < (const Line &rhs) const{
            return y<rhs.y;
        }
        Line(){}
        Line(double y,int flag,int id):y(y),flag(flag),id(id){}
    }li[N*2];
    
    double t[N*2],sum[N*8];
    int cnt[N*8];//有2*n个点 
    int v[N*2];
    //没有访问区间，不需要pushdown 
    void push_up(int x,int l,int r)
    {
        if(cnt[x]) sum[x]=t[r+1]-t[l];
        else if (l==r) sum[x]=0;
        else sum[x]=sum[x+x]+sum[x+x+1];
    }
    
    void update(int x,int l,int r,int L,int R,int upd)
    {
        if(L>R) return;
        if(L<=l&&r<=R) 
        {
            cnt[x]+=upd;
            push_up(x,l,r);//之前sum直接更新，没有考虑0或1两种情况 
            return;
        }
        int mid=(l+r)>>1;
        if(mid>=L) update(x+x,l,mid,L,R,upd);
        if(mid<R) update(x+x+1,mid+1,r,L,R,upd);
        push_up(x,l,r);
    }
    
    void build(int x,int l,int r)
    {
        if(l==r) 
        {
            sum[x]=0; cnt[x]=0;
            return;
        }
        int mid=(l+r)>>1;
        build(x+x,l,mid);
        build(x+x+1,mid+1,r);
    }
    
    void printans(double ans,int tot)
    {
        printf("Test case #%d\nTotal explored area: %.2f\n\n",tot,ans);
    }
    
    int tot=0;
    int main()
    {
        while(scanf("%d",&n)!=EOF&&n)
        {
            double ans=0; tot++;
            for(int i=1;i<=n;i++) 
            {
                scanf("%lf%lf%lf%lf",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
                t[i*2-1]=a[i].x1; t[i*2]=a[i].x2;
                li[i*2-1]=Line(a[i].y1,1,i);
                li[i*2]=Line(a[i].y2,-1,i);
            }
            sort(t+1,t+2*n+1);
            sort(li+1,li+2*n+1);
            int m=unique(t+1,t+n+n+1)-t-1;
            for(int i=1;i<=n;i++)
            {
                a[i].x1=lower_bound(t+1,t+m+1,a[i].x1)-t;
                a[i].x2=lower_bound(t+1,t+m+1,a[i].x2)-t;
            }
            build(1,1,m-1);
            for(int i=1;i<=2*n;i++)
            {
                if(i>1&&li[i].y>li[i-1].y)
                {
                    double delta=li[i].y-li[i-1].y;
                    ans+=delta*sum[1];
                }
                update(1,1,m-1,a[li[i].id].x1,a[li[i].id].x2-1,li[i].flag);
                //segtree里的i代表i~i+1区间 
            }
            printans(ans,tot);
        }
        return 0;
    }

[洛谷P1856——\[USACO5.5\]矩形周长Picture][P1856_USACO5.5_Picture]（矩形周长并）

想法类似，但做法不同。

我们还是考虑搜到每一条扫描线时的对答案的贡献，上、下位边都会有影响。

所以我们对每一条扫描线，在插入该线的前后都进行一次查询，两次剩余区间的长度之差就是该扫描线所产生的贡献。

因为有横线有竖线，所以我们对于$x,y$进行两轮扫描就可以啦~~（这道题不用离散化呦~）

注意点：可能会有两条扫描线重合，这在矩阵面积时不会产生影响，但在周长方面会产生影响。（因为可能一个矩形的上位边和一个矩形的下位边重合，我们如果顺序不当先扫到上位边，就会把原先覆盖的区间删掉，导致前后状态不同，答案更新；扫相同高度的另一个矩形的下位边时又因为区间被删掉了，再覆盖又更新了一次答案。本来上下位边重合不产生贡献，但我们这里产生了两次贡献，所以要改进一下）

我们在对扫描线进行排序时同时记录它是上位边还是下位边，作为第二关键字，使下位边排在前面就可以了

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    const int N=102000;
    
    int n;
    struct segtree{
        int cnt,sum;
    }tree[N*8];
    struct node{
        int x1,y1,x2,y2;
    }a[N];
    struct Line{
        int val,flag;
        int lz,rz;
        Line(){
        }
        Line(int val,int flag,int lz,int rz):val(val),flag(flag),lz(lz),rz(rz){
        }
        bool operator < (const Line &rhs) const{
            if(val!=rhs.val) return val<rhs.val;
            return flag>rhs.flag;
        }
    }X[2*N],Y[2*N];
    
    void build(int x,int l,int r)
    {
        if(l==r)
        {
            tree[x].cnt=tree[x].sum=0;
            return;
        }
        int mid=l+r>>1;
        build(x+x,l,mid);
        build(x+x+1,mid+1,r);
    }
    
    void pushup(int x,int l,int r)
    {
        if(tree[x].cnt) tree[x].sum=r-l+1;//之前没+1 
        else tree[x].sum=tree[x+x].sum+tree[x+x+1].sum;
    }
    
    void update(int x,int l,int r,int L,int R,int upd)
    {
        if(L>R) return;
        if(L<=l&&r<=R)
        {
            tree[x].cnt+=upd;
            pushup(x,l,r);
            return;
        }
        int mid=(l+r)>>1;
        if(mid>=L) update(x+x,l,mid,L,R,upd);
        if(mid<R) update(x+x+1,mid+1,r,L,R,upd);
        pushup(x,l,r);
    }
    
    int _abs(int x)
    {
        if(x<0) x=-x; return x;
    }
    
    int main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++) 
        {
            scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
            a[i].x1+=N; a[i].x2+=N; a[i].y1+=N; a[i].y2+=N;
            X[i*2-1]=Line(a[i].x1,1,a[i].y1,a[i].y2);
            X[i*2]=Line(a[i].x2,-1,a[i].y1,a[i].y2);//heng
            Y[i*2-1]=Line(a[i].y1,1,a[i].x1,a[i].x2);
            Y[i*2]=Line(a[i].y2,-1,a[i].x1,a[i].x2);//shu
        }
        int ans=0;
        int m=N+N;
        build(1,1,m);
        sort(X+1,X+n+n+1);
        for(int i=1;i<=n+n;i++)
        {
            int last=tree[1].sum;
            update(1,1,m,X[i].lz,X[i].rz-1,X[i].flag);//区间！要rz-1 
            int now=tree[1].sum;
            ans+=_abs(now-last);
        }
        build(1,1,m);
        sort(Y+1,Y+n+n+1);
        for(int i=1;i<=n+n;i++)
        {
            int last=tree[1].sum;
            update(1,1,m,Y[i].lz,Y[i].rz-1,Y[i].flag);//区间！要rz-1 
            int now=tree[1].sum;
            ans+=_abs(now-last);
        }
        cout<<ans<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/Forever-666/p/11330097.html

[POJ1151_Atlantis]: http://poj.org/problem?id=1151
[P1856_USACO5.5_Picture]: https://www.luogu.org/problem/P1856