扫描线学习笔记

这篇学习笔记写的没有这篇题解好/kk

扫描线是一种线段树的巧妙运用，通常用来解决一些图形的面积/周长问题。

先从最经典的问题入手：

求 n 个矩形的面积并。

—— P5490 【模板】扫描线

首先画个图，最烦人的肯定是下面这种情况：

两个矩形有相交的部分，最朴素的想法当然是减掉它。但是我们求的是 $n$ 个矩形的面积并，所以不可行。

我们可以转换一下思维，把图中所有与 $Y$ 轴平行的线段都标红、延长（称其为扫描线），可以得到这样的一个图：

很容易发现，这四条扫描线把矩形割开了，而相邻的两条线之间的部分一定是规则的矩形。

于是我们可以考虑使用某种数据结构维护两条扫描线之间的矩形投影到 $X$ 轴之后的总长度。很显然这东西能用线段树维护，让线段树的 $sum_u$ 存储节点 $u$ 所代表的区间中被矩形覆盖的长度， $all_u$ 储存节点 $u$ 所代表的区间共被多少个矩形完全覆盖， $sum_1$ 就是总长度了。

但还有一个问题，那就是坐标有可能非常大，所以我们需要对 $x$ 坐标进行离散化，然后让节点 $u$ 维护 $[pos_{l_u},pos_{r_u+1}]$ 的信息。

模板题代码：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

struct node
{
	long long y,lx,rx;
	bool in;
}a[2000005];

int n;
int tot;
long long pos[2000005];
int all[8000005];
long long sum[8000005];

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

inline void upd(int u,int l,int r)
{
	if(all[u]!=0)
	{
		sum[u]=pos[r+1]-pos[l];
	}
	else
	{
		sum[u]=sum[u<<1]+sum[u<<1|1];
	}
}

void add(int u,int l,int r,long long L,long long R,int val)
{
	if(pos[l]>=L&&pos[r+1]<=R)
	{
		all[u]+=val;
		upd(u,l,r);
		return;
	}
	int mid=l+r>>1;
	if(L<pos[mid+1])
	{
		add(u<<1,l,mid,L,R,val);
	}
	if(R>pos[mid+1])
	{
		add(u<<1|1,mid+1,r,L,R,val);
	}
	upd(u,l,r);
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		long long x1,y1,x2,y2;
		scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
		long long lx=min(x1,x2),rx=max(x1,x2),ly=min(y1,y2),ry=max(y1,y2);
		pos[++tot]=lx;
		a[tot]=(node){ry,lx,rx,true};
		pos[++tot]=rx;
		a[tot]=(node){ly,lx,rx,false};
	}
	sort(a+1,a+n*2+1,cmp);
	sort(pos+1,pos+tot+1);
	tot=unique(pos+1,pos+tot+1)-(pos+1);
	long long ans=0;
	for(int i=1;i<n*2;i++)
	{
		add(1,1,tot-1,a[i].lx,a[i].rx,a[i].in?1:-1);
		ans+=sum[1]*(a[i+1].y-a[i].y);
	}
	printf("%lld\n",ans);
	return 0;
}

不过给P1856 [IOI1998] [USACO5.5] 矩形周长Picture的更简单的解法。其实可以先按 $x$ 轴扫描一下这些矩形，再按 $y$ 轴扫描一下这些矩形，最后将扫描得到的周长相加就可以了，完全不用题解区里那么难。

完整代码：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

struct nodey
{
	long long y,lx,rx;
	bool inl;
}liny[200005];

struct nodex
{
	long long x,ly,ry;
	bool inl;
}linx[200005];

int n;
int tot[2];
long long pos[2][200005];
long long sum[2][800005];
int all[2][800005];

inline long long ckjabs(long long x)
{
	return x<0?-x:x;
}

inline bool cmpy(nodey x,nodey y)
{
	return x.y<y.y;
}

inline bool cmpx(nodex x,nodex y)
{
	return x.x<y.x;
}

inline void upd(int id,int u,int l,int r)
{
	if(all[id][u]!=0)
	{
		sum[id][u]=pos[id][r+1]-pos[id][l];
	}
	else
	{
		sum[id][u]=sum[id][u<<1]+sum[id][u<<1|1];
	}
}

void add(int id,int u,int l,int r,long long L,long long R,int val)
{
	if(pos[id][l]>=L&&pos[id][r+1]<=R)
	{
		all[id][u]+=val;
		upd(id,u,l,r);
		return;
	}
	int mid=l+r>>1;
	if(L<pos[id][mid+1])
	{
		add(id,u<<1,l,mid,L,R,val);
	}
	if(R>pos[id][mid+1])
	{
		add(id,u<<1|1,mid+1,r,L,R,val);
	}
	upd(id,u,l,r);
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		long long x1,y1,x2,y2;
		scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
		long long lx=min(x1,x2),rx=max(x1,x2);
		long long ly=min(y1,y2),ry=max(y1,y2);
		pos[0][++tot[0]]=lx;
		pos[0][++tot[0]]=rx;
		pos[1][++tot[1]]=ly;
		pos[1][++tot[1]]=ry;
		liny[i]=(nodey){ly,lx,rx,true};
		liny[n+i]=(nodey){ry,lx,rx,false};
		linx[i]=(nodex){lx,ly,ry,true};
		linx[n+i]=(nodex){rx,ly,ry,false};
	}
	sort(liny+1,liny+n*2+1,cmpy);
	sort(linx+1,linx+n*2+1,cmpx);
	sort(pos[0]+1,pos[0]+tot[0]+1);
	sort(pos[1]+1,pos[1]+tot[1]+1);
	tot[0]=unique(pos[0]+1,pos[0]+tot[0]+1)-(pos[0]+1);
	tot[1]=unique(pos[1]+1,pos[1]+tot[1]+1)-(pos[1]+1);
	long long ans=0;
	long long lst=0;
	for(int i=1;i<n*2;i++)
	{
		add(0,1,1,tot[0]-1,liny[i].lx,liny[i].rx,liny[i].inl?1:-1);
		ans+=ckjabs(sum[0][1]-lst);
		lst=sum[0][1]; 
	}
	ans+=lst;
	lst=0;
	for(int i=1;i<n*2;i++)
	{
		add(1,1,1,tot[1]-1,linx[i].ly,linx[i].ry,linx[i].inl?1:-1);
		ans+=ckjabs(sum[1][1]-lst);
		lst=sum[1][1];
	}
	ans+=lst;
	printf("%lld\n",ans);
	return 0;
}

感谢您的支持，我会继续努力的!