首页 > 其他分享 >扫描线(计算几何)

扫描线(计算几何)

时间:2023-02-25 22:24:42浏览次数:59  
标签:cnt 扫描线 int tree xaxis tag 计算 几何

semi-AFO 选手的 DS 记录(

您将在这里见到最垃圾的扫描线写法.

1. 面积

扫描线本身还是很好理解的. 偷一张图 (图源 OI-wiki)

下面的 \(cnt\) 表示对应区域被矩形覆盖的次数. 容易发现只要 \(cnt>0\) 对应的区域就会被计算到.
具体地, 我们用从下往上扫描, 遇到一个矩形的下边就对 \(cnt\) 区间加 \(1\), 上边就区间减 \(1\). 与此同时, 我们维护 \(cnt>0\) 的位置的总长度. 这样每一段扫描的面积就是这个总长度乘上扫描的高度差.

大体思路就说完了! 下面是具体实现. 先不要管线段树怎么写, 主体部分是这样的:

#define int long long//不开 long long 见祖宗
const int maxn=100010;
struct scan{int l,r,h,tag;}lines[maxn<<1];
//l,r 为左右端点的 x 坐标, h 为 y 坐标, tag=1/-1 表示下/上边
//温馨提示: 二倍空间.
bool cmp(scan s,scan ss)//按照 y 坐标排序
{
	if(s.h!=ss.h)return s.h<ss.h;
	return s.tag>ss.tag;//注意 tag 的比较顺序. 对于面积无所谓, 但之后算周长这是很重要的细节
}
int n,ans;
int xcnt,xaxis[maxn<<1];//x 坐标的范围很大, 所以我们要离散化. 这些都是离散化用的.
map<int,int> mp;
signed main()
{
	n=read();
	for(int i=1;i<=n;i++)//简单读入
	{
		int x=read(),y=read(),xx=read(),yy=read();
		lines[2*i-1]=(scan){x,xx,y,1};
		lines[2*i]=(scan){x,xx,yy,-1};
		xaxis[2*i-1]=x;xaxis[2*i]=xx;
	}
	sort(xaxis+1,xaxis+2*n+1);
	xcnt=unique(xaxis+1,xaxis+2*n+1)-xaxis-1;
	for(int i=1;i<=xcnt;i++)mp[xaxis[i]]=i;//以上为离散化.
	sort(lines+1,lines+2*n+1,cmp);//扫描线排序
	build(1,1,xcnt-1);//线段树建树, 注意线段树维护的是端点之间的区间的值, 要做好对应关系
	for(int i=1;i<=2*n;i++)
	{
		ans+=getlen()*(lines[i].h-lines[i-1].h);//算一下面积
		modify(1,mp[lines[i].l],mp[lines[i].r]-1,lines[i].tag);//区间加 1/-1, 上面说过
	}
	printf("%lld\n",ans);
	return 0;
}

很简单吧.
然后你发现问题在于线段树怎么维护 \(cnt>0\) 的位置对应的长度和.
很多人用奇怪的类似标记永久化的操作进行维护. 不过我是无脑选手, 所以我 (参考某篇题解) 这样做:
维护一下区间的 \(\min\) 和值为 \(\min\) 对应的长度和. 这样如果 \(\min=0\) 就把 \(\min\) 的长度和减掉即可.
具体实现如下 (你会发现并不需要维护 \(cnt\) 的值)

struct point{int l,r,minn,minlen,add;}tree[maxn<<3];//2*4=8 倍空间
inline void pushup(int x)
{
	int lson=x<<1,rson=lson|1;
	tree[x].minn=min(tree[lson].minn,tree[rson].minn);
	tree[x].minlen=0;
	if(tree[x].minn==tree[lson].minn)tree[x].minlen+=tree[lson].minlen;
	if(tree[x].minn==tree[rson].minn)tree[x].minlen+=tree[rson].minlen;//合理 pushup
}
inline void pushadd(int x,int k)
{
	tree[x].add+=k;
	tree[x].minn+=k;
}
inline void pushdown(int x)
{
	if(tree[x].l==tree[x].r)return;
	int lson=x<<1,rson=lson|1;
	if(tree[x].add!=0)
	{
		pushadd(lson,tree[x].add);
		pushadd(rson,tree[x].add);
		tree[x].add=0;
	}
}
void build(int x,int l,int r)
{
	tree[x]=(point){l,r,0,0,0};
	if(l==r)
	{
		tree[x].minlen=xaxis[tree[x].r+1]-xaxis[tree[x].l];//初始化对应的长度
		return;
	}
	int mid=(tree[x].l+tree[x].r)>>1,lson=x<<1,rson=lson|1;
	build(lson,l,mid);build(rson,mid+1,r);
	pushup(x);
}
void modify(int x,int l,int r,int k)
{
	pushdown(x);
	if(l<=tree[x].l&&r>=tree[x].r){pushadd(x,k);return;}
	int mid=(tree[x].l+tree[x].r)>>1,lson=x<<1,rson=lson|1;
	if(l<=mid)modify(lson,l,r,k);
	if(r>mid)modify(rson,l,r,k);
	pushup(x);
}
inline int getlen()
{
	if(tree[1].minn>0)return xaxis[tree[1].r+1]-xaxis[tree[1].l];
	else return xaxis[tree[1].r+1]-xaxis[tree[1].l]-tree[1].minlen;//如果 min 为 0 就把 minlen 减掉
}

总的代码把两段拼一起就行了(

2. 周长

把面积的代码稍微改改就行(
只需要注意下面几个点.

  1. 具体计算方法

最简单的做法 (就是懒得多维护东西了) 是横竖分别扫一遍, 每次统计平行的边长.
你发现每次对周长的贡献就是相邻两次扫描线长度的差的绝对值. 所以就做完了!

//以计算平行于 x 轴的边长和为例
int lastlen=0;
for(int i=1;i<=2*n+1;i++)//记得把两端的也给算上
{
	int now=getlenx();
	ans+=llabs(now-lastlen);
	lastlen=now;
	if(i<2*n+1)modify(1,mpx[lines[i].l],mpx[lines[i].r]-1,lines[i].tag);
}
  1. 一个重要细节

实际上上面说过了. 就是这里对于 \(tag\) 顺序的规定:

struct scan{int l,r,h,tag;}lines[maxn<<1],lines2[maxn<<1];
bool cmp(scan s,scan ss)
{
	if(s.h!=ss.h)return s.h<ss.h;
	return s.tag>ss.tag;//这里让 tag 是 1 的放在 -1 前面
}

这是因为对于两个矩形, 如果一个的下边恰好与另一个的上边重合, 就不能急着把原来的减掉, 要不然会把中间那条多算两遍.

经典样例:

2
0 0 4 4
0 4 4 8

你的程序应当输出 24.

总代码懒得放了(

标签:cnt,扫描线,int,tree,xaxis,tag,计算,几何
From: https://www.cnblogs.com/pjykk/p/17154725.html

相关文章