HDU 1828 线段树之扫描线之周长并

点击打开链接

题意：给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;
}

最后

以上就是冷酷羊为你收集整理的HDU 1828 线段树之扫描线之周长并的全部内容，希望文章能够帮你解决HDU 1828 线段树之扫描线之周长并所遇到的程序开发问题。

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