浅谈扫描线-Toy模板网

这篇具有很好参考价值的文章主要介绍了浅谈扫描线。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

扫描线

扫描线一般运用在图形上面，它和它的字面意思非常相似，就是拿一根线，在图形上面扫来扫去。我们一般用它来解决图形的面积，周长，二位数点等问题。

Atlantis 问题

在二维坐标系上，给出多个矩形的左下以及右上坐标，求出所有矩形构成的图形的面积。

我们当然知道，如果数据范围很小，我们可以直接暴力，也就是先都加起来，然后再枚举一下把重复的减去；但如果数据范围过大，我们暴力肯定是不行的，这个时候就可以用到我们的扫描线了。

假设我们现在有一根线，从下往上开始扫描：

（这是张动图可能导成pdf就挂了）

我们发现，我们把整个图形分成了如图各个颜色不同的小矩形，那么这个小矩阵的高就是我们扫过的距离，那么剩下了一个变量，那就是长在不断地变化。

我们一般用线段树来维护矩形的长，我们给每一个矩形的上下边进行标记，下面的边标记为 $1$，上面的边标记为 $-1$，每遇到一个矩形的时候，我们就知道了标记为 $1$ 的边，我们就加进来这一条矩形的长，等到扫描到 $-1$ 的时候，证明这一条边需要删除，就删去，利用 $1$ 和 $-1$ 可以轻松的到达这种状态。

我们一般还需要用到离散化。

面积并

我们结合例题来看一下：

P5490【模板】扫描线 - 洛谷

我们前面说要用线段树来做，我们用它来维护当前的矩形的长。

我们考虑到我们的线段树维护的东西都是点，但是我们需要维护的是区间，那么我们可以把区间下放到点上，也就是每一个叶子节点维护的是一个线段，而我们用 $l$，也就是当前点的左端点，以及 $r+1 $ 来达到询问当前节点区间的左右端点的目的。

我们先来看主函数：

signed main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        x11=read(),y11=read(),x22=read(),y22=read();
        X[2*i-1]=x11,X[2*i]=x22;
        e[2*i-1]=(sb){x11,x22,y11,1};
        e[2*i]=(sb){x11,x22,y22,-1};
    }
    n*=2;
    sort(e+1,e+n+1,cmp);
    sort(X+1,X+n+1);
    int tot=unique(X+1,X+n+1)-X-1;
//    cout<<"tot:"<<tot<<endl;
    build(1,1,tot-1);
    int ans=0;
    for(int i=1;i<n;i++)
    {
        change(1,e[i].l,e[i].r,e[i].flag);
        ans+=e1[1].len*(e[i+1].h-e[i].h);
    }
    cout<<ans<<endl;
//    for(int i=1;i<=n;i++)cout<<X[i]<<" ";cout<<endl;
    return 0;
}

$X$ 数组是用来存放所有点的横坐标，因为我们是要维护区间的话，不可能每一个点都维护到，所以只存放有给定点的坐标，$e$ 是定义的结构体用于存放每一个矩形的信息，我们需要把他给存放下当前矩形的信息，其中 $X[2i-1]$ 是当前矩形的左端点横坐标，$X[2i]$ 是当前矩形的右端点横坐标，$e[2i-1]$ 是当前矩形的下表面，$e[2i]$ 是当前矩形的上表面，因为我们说了如果要是碰到了下表面，我们就需要给他加进去，一旦碰到上表面，说明这个矩形完成了，可以出去了。两个 sort 第一个是给矩形的上下表面按高度排序，保证是从下往上遍历的，不会出现负数，后面的是进行排序后用 unique 进行离散化，然后就开始建树。因为我们是把线段放到左端点上，所以是 $tot-1$ 个。再往后，我们进行 change 操作来对当前扫到的矩形长的长度做修改，然后用上一个的高度减去当前点的高度，计算当前扫到的面积。

再来看 change 操作：

inline void p_p(int x)
{
    int l=e1[x].l,r=e1[x].r;
    if(e1[x].sum)e1[x].len=X[r+1]-X[l];
    else e1[x].len=e1[ls].len+e1[rs].len; 
}
inline void change(int x,int nl,int nr,int c)
{
    int l=e1[x].l,r=e1[x].r;
    if(X[r+1]<=nl||nr<=X[l])return ;
    if(nl<=X[l]&&X[r+1]<=nr)
    {
        e1[x].sum+=c;
        p_p(x);
        return ;
    }
    change(ls,nl,nr,c);
    change(rs,nl,nr,c);
    p_p(x);
    return ;
}

我们的 change 里面是用来修改当前扫到的矩形的长的长度总和的。

如果要是当前的区间右端点在要改的左端点的左边，那肯定不会包含，直接退出；如果当前区间左端点在要改的右端点的右边，那肯定也不包含，直接退出。

后面如果遇到包含的区间就直接改 $sum$，然后更新。

这个更新函数也就是 p_p 是对于所有的扫到的线段长度进行求和返回到上面，如果没有扫到就直接更新儿子节点，为什么呢？因为一开始的儿子节点长度都是 $0$，叶子节点没有儿子节点，默认也是 $0$。

至此我们完成了这个奇妙的算法！

周长并

既然求了面积，那就再来看看求周长吧。

P1856[IOI1998] [USACO5.5] 矩形周长Picture - 洛谷

~~看到题目给的图片：什么乱七八糟的~~

我们来试着找找有没有什么规律：

我们先来看竖着的线。

浅谈扫描线

我们很容易发现，我们当前截到的线段数量，乘上 $2$，然后再乘以当前点扫过的高度，不就是我们当前扫到的所有矩形的竖边的长度总和吗？

然后我们再来看横边。

浅谈扫描线

我们手模一下不难发现，我们在往上不断平移线段的时候，我们发现，当前的长，也就是和线段重合的长度，是上一次的长度与这次长度做差的绝对值！

为什么是绝对值？如果是一开始的时候，长会越来越大，就是这一次减去上一次的值，而到了后面，就是上一次长度减去这一次长度的值了。

所以我们需要加个绝对值。

知道怎么算周长了，那我们直接套线段树吧！

但是我们上面说过，计算竖边的时候，我们需要知道当前扫描线上线段的数量。

所以我们的线段树要多维护几个东西：当前线段左右端点是否被覆盖，以及当前区间内扫描线上的线段数量。

具体结合代码来分析：

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x11>>y11>>x22>>y22;
        X[2*i-1]=x11,X[2*i]=x22;
        e[2*i-1]={x11,x22,y11,1};
        e[2*i]={x11,x22,y22,-1};
    }
    n*=2;
    sort(e+1,e+n+1,cmp);
    sort(X+1,X+n+1);
    int tot=unique(X+1,X+n+1)-X-1;
    build(1,1,tot-1);
    int res=0;
    for(int i=1;i<n;i++)
    {
        change(1,e[i].l,e[i].r,e[i].flag);
        res+=abs(pre-t[1].len);
        pre=t[1].len;
        res+=2*t[1].c*(e[i+1].h-e[i].h);
    }
    res+=e[n].r-e[n].l;
    cout<<res<<endl;
    return 0;
}

和上面一样的部分就不说了，看不一样的。

对 $e$ 进行排序的时候，我们先按高度排序，然后高度相同就把下底面放前面，因为不这样做就会把这条边多扫一遍，虽然在面积中无影响但是对于周长影响挺大的。

其中 $pre$ 表示上一次扫描线上的线段总长度。

最后为什么有一个第 $n$ 个矩形的单独计算呢？因为我们上面是枚举到 $n-1$，最后一条边是取不到的，所以我们最后算上。

inline void p_p(int x)
{
    int l=t[x].l,r=t[x].r;
    if(t[x].sum)
    {
        t[x].len=X[r+1]-X[l];
        t[x].lc=t[x].rc=1;
        t[x].c=1;
    }
    else 
    {
        t[x].len=t[ls].len+t[rs].len;
        t[x].lc=t[ls].lc,t[x].rc=t[rs].rc;
        t[x].c=t[ls].c+t[rs].c;
        if(t[rs].lc&&t[ls].rc)t[x].c--;
    }
}
inline void change(int x,int nl,int nr,int c)
{
    int l=t[x].l,r=t[x].r;
    if(X[l]>=nr||nl>=X[r+1])return ;
    if(nl<=X[l]&&nr>=X[r+1])
    {
        t[x].sum+=c;
        p_p(x);
        return ;
    }
    change(ls,nl,nr,c);
    change(rs,nl,nr,c);
    p_p(x);
    return ; 
}

更新函数里面，$lc,rc$ 分别表示当前节点代表的线段的左右端点是否被覆盖，$c$ 是此区间内的线段数量，如果 $sum$ 有值，我们就直接更新，标记当前线段左右端点都被覆盖，然后就是当前区间是一个线段，$c$ 标记为 $1$。

如果此区间内不是都被覆盖，那就先累加长度，随后判断此区间的端点覆盖情况，如果左区间左端点被覆盖，那么此区间的左端点也被覆盖，反之对于右区间的右端点也成立，先粗略把左右区间的线段数累加起来，后面判断交点是否都被覆盖，如果都被覆盖，说明中间是一整段的，直接把线段树减一即可。

对于 change 函数，和之前的面积修改一样。

然后我们就把周长的问题也给解决了！

但是扫描线的作用不仅限于此。