我是靠谱客的博主 等待手机,最近开发中收集的这篇文章主要介绍线段树之扫描线之周长并,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

题意:给n个矩形,求它们重叠后的周长
思路:用线段树的扫描线从下到上扫一遍,与面积并思想有些相似面积并,下面重边的处理相似,但是周长的并需要求的是竖边的个数然后乘以高度,而面积并求的是底边的长乘以高度,这里我们用了区间合并时的lnum和rnum,具体下面有注释

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <iostream>

#include <algorithm>

using namespace std;
typedef long long ll;
const int maxn=50010;
int num[maxn*4],num1[maxn*4],X[maxn],numseg[maxn*4];//numseg是目前加进去了多少条竖边

bool lnum[maxn*4],rnum[maxn*4];//num代表的是底边的长度

//lsum代表当前节点所代表的区间左侧是否有竖边,rsum代表当前节点的右侧是否有竖边,与线段树区间合并很相似

struct edge{
int l,r,h,s;//s为1是下边,为-1是上边

edge(){}
edge(int a,int b,int c,int d) : l(a),r(b),h(c),s(d) {}
bool operator <(const edge &n) const{
if(n.h==h) return s>n.s;
return h<n.h;
}
}ss[maxn];
void pushup(int le,int ri,int node){
if(num1[node]){
lnum[node]=rnum[node]=1;
num[node]=ri-le+1;//传入节点也是和面积并一样,防止重边的计算

numseg[node]=2;//加入一条新边,则多两条竖边

}else if(le==ri) num[node]=lnum[node]=rnum[node]=numseg[node]=0;
else{
lnum[node]=lnum[node<<1];
rnum[node]=rnum[node<<1|1];
num[node]=num[node<<1]+num[node<<1|1];
numseg[node]=numseg[node<<1]+numseg[node<<1|1];
if(lnum[node<<1|1]&&rnum[node<<1]) numseg[node]-=2;
//如果左区间的右端点与右区间的左端点都等于1的话,说明这个端点被覆盖了,所以减去2

}
}
void update(int l,int r,int add,int le,int ri,int node){
if(l<=le&&ri<=r){
num1[node]+=add;
pushup(le,ri,node);
return ;
}
int t=(le+ri)>>1;
if(l<=t) update(l,r,add,le,t,node<<1);
if(r>t) update(l,r,add,t+1,ri,node<<1|1);
pushup(le,ri,node);
}
int main(){
int n;
while(scanf("%d",&n)!=-1){
int k=0,lmax=999999,rmax=-999999;//点的范围并不大,不需要离散化,只要找到最左边和最右边建树就行了

for(int i=0;i<n;i++){
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
lmax=min(lmax,a);
rmax=max(rmax,c);
ss[k++]=edge(a,c,b,1);
ss[k++]=edge(a,c,d,-1);
}
sort(ss,ss+k);
int ans=0,last=0;
for(int i=0;i<k;i++){
if(ss[i].l<ss[i].r) update(ss[i].l,ss[i].r-1,ss[i].s,lmax,rmax-1,1);
ans+=numseg[1]*(ss[i+1].h-ss[i].h);//将竖边的个数乘以高度加起来

ans+=abs(num[1]-last);//加上底边的长度,因为这个是长度,不像面积,不管是上边还是下边都要加起来

last=num[1];//所以我们将last作为上次的状态,num[1]大于last说明加入了边,肯定是要加上的

}
//然后如果num[1]小于last说明有一条上边加入,因为上边是-1,所以将上边的值减去了,

//但是我们要加上它,所以用绝对值解决这个问题

printf("%dn",ans);
}
return 0;
}

最后

以上就是等待手机为你收集整理的线段树之扫描线之周长并的全部内容,希望文章能够帮你解决线段树之扫描线之周长并所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(40)

评论列表共有 0 条评论

立即
投稿
返回
顶部