hdu1828（线段树+扫描线求周长）

59 阅读 0 评论 39 点赞

我是靠谱客的博主爱笑金毛，最近开发中收集的这篇文章主要介绍hdu1828（线段树+扫描线求周长），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这题不错，可以更加深入的了解线段树扫面线算法，大家之前可能做过扫描线求矩形面积，但因为求面积的某些局限性，一些细节不用写到就可以a，但求周长不行。

首先，介绍下求周长的思路，从左往右在每一次插入一条边后，周长并的累加值==新增的横边+新增的竖边。我们可以发现，插入一条边之后，新增的横边的树木等于区间内连续线段的数目*新增横边的长度，新增的竖边等于插入前后覆盖长度的差值。插入一条出边之后，其实等同于删除该矩形对应的入边。出现了不连续的线段了。横边也相应增加了。这个思路比较好想到。

接着是实现的问题，前后覆盖的长度的插值比较好求，扫描线模板就行，求每次插入后有几段连续的线段，这个不就是so low的区间合并吗。

最后讲一下注意的细节，在求面积的过程中，大家可能都没有去掉重复的值，但在这里不去掉是不行的。我们要求连续的区间个数必须要维护三个值，整个区间内线段的个数，左边是否被覆盖，右边是否被覆盖。比如一个区间a的两个子区间是b1[10,30],b2[30,30],那么我们插入[10,30]时会覆盖b2[10,30]，另一个区间c[30,40]如果c被全部覆盖，那要求a，c的总区间的线段个数，其中一步就是要看a的右边和c的左边是否被覆盖，在实际情况中a的右边被覆盖，但由于b2这个点没有被更新，所以它是没有被覆盖，这里就会出问题。到这时候，楼主交hdu的G++wa，c++a了。。。。坑啊！！！后来发现一组数据过不了。

10 10 30 30

30 10 50 30

这两个矩形有两条边完全重合，如果我们只安x的大小排序，会先算第一个矩形的出边，周长加上20，再算第二个矩形的入边，会加上20，我们在排序时，如果x相等，则把入边放前面。大家可以自行体会。下面附上代码

#include <iostream>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<cstring>
using namespace std;
const int MAX=2*1e4+20;
int N;
int y[MAX];
int sum=0;
typedef struct{
int x,y1,y2;
int f;
void set(int xx,int yy1,int yy2,int ff)
{
x=xx;
y1=yy1;
y2=yy2;
f=ff;
}
}Node;
Node no[MAX];
typedef struct
{
int left,right;
int cover;
int realleft,realright,len;
int lflag,rflag,cnt;
void set(int l,int r)
{
lflag=rflag=cnt=0;
left=l;
right=r;
cover=0;
len=0;
realleft=y[l];
realright=y[r];
}
}P;
P per[4*MAX];
bool cmp(const Node &n1,const Node &n2)
{
if(n1.x!=n2.x)
return n1.x<n2.x;
else
return n1.f>n2.f;
}
void build(int id,int left,int right)
{
per[id].set(left,right);
if(right-left==1)
return;
int mid=(left+right)/2;
build(id<<1,left,mid);
build(id<<1|1,mid,right);
}
void get_len(int t)
{
if(per[t].cover>0)
{
per[t].len=per[t].realright-per[t].realleft;
per[t].cnt=per[t].lflag=per[t].rflag=1;
}
else
if(per[t].left+1==per[t].right)
{
per[t].len=0;
per[t].cnt=per[t].lflag=per[t].rflag=0;
}
else
{
per[t].len=per[t<<1].len+per[t<<1|1].len;
per[t].lflag=per[t<<1].lflag;
per[t].rflag=per[t<<1|1].rflag;
per[t].cnt=per[t<<1].cnt+per[t<<1|1].cnt-per[t<<1].rflag*per[t<<1|1].lflag;
}
}
void update(int id,Node node)
{
if(per[id].realleft==node.y1&&per[id].realright==node.y2)
{
per[id].cover+=node.f;
get_len(id);
return;
}
if(per[id<<1].realright>=node.y2)
update(id<<1,node);
else
if(per[id<<1|1].realleft<=node.y1)
update(id<<1|1,node);
else
{
Node m=node;
m.y2=per[id<<1].realright;
update(id<<1,m);
m=node;
m.y1=per[id<<1|1].realleft;
update(id<<1|1,m);
}
get_len(id);
}
int main()
{
int x1,x2,y1,y2;
int num=1;
while(scanf("%d",&N)!=EOF)
{
memset(y,0,sizeof(y));
sum=0;
int t=0;
for(int i=0;i<N;i++)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
no[t].set(x1,y1,y2,1);
y[t]=y1;
t++;
no[t].set(x2,y1,y2,-1);
y[t]=y2;
t++;
}
sort(no,no+t,cmp);
sort(y,y+t);
int le=0;
y[le++]=y[0];
for(int i=1;i<t;i++)
if(y[i]!=y[i-1])
y[le++]=y[i];
build(1,0,le-1);
int d=0;
for(int i=0;i<t-1;i++)
{
update(1,no[i]);
sum+=abs(per[1].len-d);
d=per[1].len;
sum+=2*per[1].cnt*( no[i+1].x-no[i].x);
}
update(1,no[t-1]);
sum+=abs(per[1].len-d);
cout<<sum<<endl;
}
return 0;
}