浅谈扫描线

Atserckcn · 2026-09-10 13:30:10 · 算法·理论

浅谈扫描线

前置知识

• 离散化
• 线段树
• 平面几何。？

前言

发现网上大部分题解貌似对于本质没有讲得很明白？

反正自己学时是走了挺多弯路的，在这里总结下，也算为 OI 事业做贡献。？

攒攒 RP。

情景

给定一个坐标系，上面有若干矩形，需要维护它们之间的信息。

扫描线在网络中有从左往右和从下往上扫两种阵营，本文属于后者。

若无特殊说明，均为以 y 坐标从小到大扫描。

一般是将矩形的上下边拆出来，按照 y 坐标排序，将上下边赋予不同的权值，再用线段树维护 x 轴上元素的信息。

元素可能是线段（区间）也可能是点。

求面积并

例题：P5490 【模板】扫描线 & 矩形面积并。

这题貌似题解满街都是，图也可以去 oi-wiki 看，这里就不放了。

考虑将一个以 (x_1,y_1) 为左端点，(x_2,y_2) 为右端点的矩形拆出两条边，分别是 (x_1,x_2,y_1) 和 (x_1,x_2,y_2)。其中 x_1<x_2,y_1<y_2。

下文称 (x_1,x_2,y_1) 为矩形的下边，(x_1,x_2,y_2) 为矩形的上边。

我们先对每一个矩形都进行此操作，并对边按照 y 坐标从小到大排序。

首先发现矩形面积并可以拆分为若干小矩形的面积之和。

而小矩形面积又等于长乘高。高是容易的，只需要求出刚处理的相邻两条线段的 y 坐标之差即可。

那么长度呢？

注意，这里可能有若干个矩形不挨在一起，所以只统计一个区间 [l,r] 是否有矩形是不可以的。

注意到一段区间 [l,r] 能被算进小矩形面积当且仅当其被至少一个矩形包含。

而区间被矩形包含的开始就是矩形的下边。

考虑维护 x 轴的每个区间是否被包含，等价于维护是否存在至少一条在该区间下方的下边。

而如果有两条下边重合了，重合的那段区间需要计算两次。

所以可以考虑用线段树维护每个 x 轴的区间被包含了多少次，遇到下边就将区间 [x_1,x_2] 整体加一，上边就减一。

然后所有被包含的区间长度总和就是线段树中所有值不为 0 的元素个数。

这里动态开点貌似也可以，但是离散化一下会更好。

然后如何维护就是个人认为网上讲得不是很详细的一点了。

我们令 x 代表 [x,x+1] 这段区间。

显然一段长度为一的区间左端点是 l，右端点是 l+1，而区间加的 [p,q] 是不包含以 q 为左端点的区间的。

这才有了所谓的“端点偏移”。

剩下的就是代码实现了，不想写注释，不懂可以参考模板题的题解。

给个代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ljl;
#define y1 Atserckcn_CSPS2026_yidengjiang
const int N=1e5+5;
int n,tot,cx;
ljl ans,X[N<<1];
struct Line{
    ljl l,r,y,op;
    bool operator < (const Line a)const{
        return y<a.y;}
}l[N<<1];
struct NODE{
    ljl l,r,cnt,cv;
}node[N*2*4];
#define lc (p<<1)
#define rc (p<<1|1)
void pushup(int p)
{
    if(node[p].cv){node[p].cnt=X[node[p].r+1]-X[node[p].l];return;}
    if(node[p].l==node[p].r){node[p].cnt=0;return;}
    node[p].cnt=node[lc].cnt+node[rc].cnt;
    return;
}
void bld(int l,int r,int p)
{
    node[p].l=l;node[p].r=r;
    if(l==r)return;
    int mid=(l+r)>>1;
    bld(l,mid,lc);bld(mid+1,r,rc);
    pushup(p);
    return;
}
void addlr(int l,int r,ljl val,int p)
{
    if(l>r)return;
    if(l<=node[p].l&&node[p].r<=r)
    {
        node[p].cv+=val;
        if(node[p].cv>=1)node[p].cnt=X[node[p].r+1]-X[node[p].l];
        else pushup(p);
        return;
    }
    int mid=(node[p].l+node[p].r)>>1;
    if(l<=mid)addlr(l,r,val,lc);
    if(mid<r)addlr(l,r,val,rc);
    pushup(p);
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1,x1,x2,y1,y2;i<=n;++i)
    {
        cin>>x1>>y1>>x2>>y2;
        l[++tot].l=x1;l[tot].r=x2;l[tot].y=y1;l[tot].op=1;
        l[++tot].l=x1;l[tot].r=x2;l[tot].y=y2;l[tot].op=-1;
        X[++cx]=x1;X[++cx]=x2;
    }
    sort(X,X+cx+1);
    cx=unique(X+1,X+cx+1)-X-1;
    bld(1,cx-1,1);
    sort(l+1,l+tot+1);
    for(int i=1;i<=tot;++i)
    {
        int L=lower_bound(X+1,X+cx+1,l[i].l)-X;
        int R=lower_bound(X+1,X+cx+1,l[i].r)-X;
        if(i>1)ans+=(node[1].cnt*(l[i].y-l[i-1].y));
        addlr(L,R-1,l[i].op,1);
    }cout<<ans<<'\n';
    return 0;
}

求矩形周长

题目：P1856 [IOI 1998 USACO5.5] 矩形周长 Picture。

我去竟然是 IOI 真题吗。

这题我并没有写，只是学校数学课摸鱼时口胡了几种做法。

第一种。注意到 x 轴和 y 轴谁是谁其实不重要，所以可以先从 y 轴从下往上扫一遍，按上题一样统计有多少区间是在外面的，这要的是两次查找的长度之差的绝对值，再按 x 轴扫一遍，统计竖着的区间长度。这应该是对的，就是好麻烦。

为什么是差？因为差的是新增的。

对矩形周长差贡献的证明

发现洛谷上某篇题解是这么说的：

侵权自删。

那么怎么证明呢？

学校化学课摸鱼想到的（逃。

首先可以类比括号序列，下边是左括号，上边是右括号。则全部矩形构成了合法括号序列。

那么一条边能对答案有贡献当且仅当满足下列一个：

• 下面没边
• 上面没边

注意到这是不可能全部满足的。但这不重要。

那么类似括号序列处理，统计在能匹配的都匹配了后，还剩余的左括号（下边）的数量。

如果是 0，那么说明该边是下边（想想为什么），要计入答案。并区间加。

否则对答案就是没有贡献的。

那么上方没有边的上边该怎么计算？

注意到上边是区间减法操作，而减法后，可以计入答案当且仅当有区间因为这次操作而从 1\rightarrow 0。

综上，不管是上边还是下边能对答案做出贡献的情况都能用 ans_{cur}-ans_{lst} 表示出来。

第二种。发现扫描 y 轴的时候太浪费了，什么都没做。

发现每步扫描对答案的贡献是 A+c\times \Delta y。其中 \Delta y 是相邻两边的 y 轴坐标之差。A 是两次查找的长度差，c 是有多少个点没被包含且值不为 0。

画个图理解下。

然后维护一下就做完了。

代码去题解区看看吧。

求区间最值

题：P12119 [NordicOI 2025] 垃圾收集 Garbage Collection。

首先维护矩形是困难的，考虑化矩形为点。

显然可以通过固定一个角的方式确定一个矩形。

本文以 (x,y) 表示以 (x,y) 为左下角，(x+W-1,y+H-1) 为右上角的矩形。称 (x,y) 为代表点。

那么一个垃圾 (x,y) 想要捕获它，代表点 (a,b) 就必须满足 x-W+1\le a\le x,y-H+1\le b\le y。

不懂的自行画图。

所以可以考虑将垃圾 (x,y) 转化为矩形加法，将以 (X-W+1,y-H+1) 为左下角，(x,y) 为右上角的矩形中所有整点都加上权值。

那么现在是求一个点 (x,y) 使得以其权值最大。

注意：上文我们讨论的扫描线都是维护线段（区间），但这里是点，所以不需要端点偏移。

考虑将转化后的矩形的下边权值赋为 w，上边赋为 -w。

这样按照 y 坐标排序，每次操作完对所有点取 \max 就好了。

吗？

并不是！

注意到我们是可以取到 y 坐标和上边一样高度的点的，如果只看 y 进行排序很有可能会优先减掉贡献，就无法算出正确答案。

那么怎么修改？

这里我搞出了两种。

• 以 y 为第一关键字从小到大排，w 为第二关键字从大到小排。

这样因为上边的权值是负数，一定没有下边的权值大，所以每次都会优先加入下边。

• 将上边的 y 坐标加一，再比较完 y 后按照 w 从小到大排。

这里的上边可以表示“不可以取到这个高度”的意思，所以要优先限制，再计算。

给出代码。

第一种的排序：

struct Lines{
    ljl l,r,y,w;
    bool operator < (const Lines a)const{
        if(y!=a.y)
            return y<a.y;
        return w>a.w;
    }
}lns[N*2];

建立线段：

lns[++tot].l=x-W+1;lns[tot].r=x;lns[tot].y=y-H+1;lns[tot].w=w;
lns[++tot].l=x-W+1;lns[tot].r=x;lns[tot].y=y;lns[tot].w=-w; 

第二种排序：

struct Lines{
    ljl l,r,y,w;
    bool operator < (const Lines a)const{
        if(y!=a.y)
            return y<a.y;
        return w<a.w;
    }
}lns[N*2];

建立线段：

lns[++tot].l=x-W+1;lns[tot].r=x;lns[tot].y=y-H+1;lns[tot].w=w;
lns[++tot].l=x-W+1;lns[tot].r=x;lns[tot].y=y+1;lns[tot].w=-w;   

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ljl;
const int N=1e5+5;
int n,tot;
ljl W,H,X[N*2],cx,ans;
struct Lines{
    ljl l,r,y,w;
    bool operator < (const Lines a)const{
        if(y!=a.y)
            return y<a.y;
        return w<a.w;
    }
}lns[N*2];
struct NODE{
    int l,r;ljl lz,maxn;
}node[N*2*4];
#define lc (p<<1)
#define rc (p<<1|1)
void pushup(int p)
{
    if(node[p].l==node[p].r)return;
    node[p].maxn=max(node[lc].maxn,node[rc].maxn);
    return;
}
void bld(int l,int r,int p)
{
    node[p].l=l;node[p].r=r;
    if(l==r)return;
    int mid=(l+r)>>1;
    bld(l,mid,lc);bld(mid+1,r,rc);
    pushup(p);
    return;
}
void pushdown(int p)
{
    if(!node[p].lz)return;
    if(node[p].l==node[p].r)return;
    node[lc].lz+=node[p].lz;
    node[rc].lz+=node[p].lz;
    node[lc].maxn+=node[p].lz;
    node[rc].maxn+=node[p].lz;
    node[p].lz=0;
    return;
}
void addlr(int l,int r,ljl val,int p)
{
    if(l<=node[p].l&&node[p].r<=r)
    {
        node[p].maxn+=val;node[p].lz+=val;
        return;
    }
    pushdown(p);
    int mid=(node[p].l+node[p].r)/2;
    if(l<=mid)addlr(l,r,val,lc);
    if(mid<r)addlr(l,r,val,rc);
    pushup(p);
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>W>>H;
    for(ljl i=1,x,y,w;i<=n;++i)
    {
        cin>>x>>y>>w;
        lns[++tot].l=x-W+1;lns[tot].r=x;lns[tot].y=y-H+1;lns[tot].w=w;
        lns[++tot].l=x-W+1;lns[tot].r=x;lns[tot].y=y+1;lns[tot].w=-w;       
        X[++cx]=x-W+1;X[++cx]=x;
    }
    sort(lns+1,lns+tot+1);
//  cout<<"---------\n";
//  for(int i=1;i<=tot;++i)cout<<lns[i].l<<' '<<lns[i].r<<' '<<lns[i].y<<'\n';
//  cout<<"---------\n";
    sort(X+1,X+cx+1);
    cx=unique(X+1,X+cx+1)-X-1;
//  for(int i=1;i<=cx;++i)cout<<X[i]<<' ';
//  cout<<'\n';
    bld(1,cx,1);
    for(int i=1;i<=tot;++i)
    {
        int l=lower_bound(X+1,X+cx+1,lns[i].l)-X;
        int r=lower_bound(X+1,X+cx+1,lns[i].r)-X;
        addlr(l,r,lns[i].w,1);
        ans=max(ans,node[1].maxn);
//      cout<<"["<<l<<','<<r<<"],add "<<lns[i].w<<'\n';
    }cout<<ans<<'\n';
    return 0;
}

后记

因为作者很弱，扫描线还有很多用法都没讲到，以后有机会补一补。

感谢 Tiger_Rory 学长把他在【数据删除】学校给【数据删除】班讲的扫描线课件分享给我！/bx

大家不要学我上课摸鱼！