poj 1177 经典线段树+扫描线就周长并

可以参考陈宏的论文，就是将矩形的线段按x轴排序后每次利用前后直接线段覆盖y值的差值计算竖线的长度，利用前后两直线直接的x周距离乘不相交线段的条数计算横线的长度。

具体可以看代码。本题坐标范围较小，可以不用离散化。

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
const int nMax=5005;
const int M=10000;
int N;
struct Line
{
int x,y1,y2,f;
}line[nMax*3];
int cmp(Line l1,Line l2)
{
return l1.x<l2.x;
}
struct Tree
{
int l,r,cov,num,clen;
int lcov,rcov;
}t[100000];
#define mid ((t[p].l+t[p].r)>>1)
#define ls (p<<1)
#define rs ((ls)+1)
void maketree(int p,int l,int r)
{
t[p].l=l;t[p].r=r;t[p].cov=t[p].num=0;
t[p].lcov=t[p].rcov=0;
if(r-l==1) return;
maketree(ls,l,mid);
maketree(rs,mid,r);
}
void pushup(int p)
{
if(t[p].cov>0)
{
t[p].clen=t[p].r-t[p].l;
t[p].num=1;
t[p].lcov=t[p].rcov=1;
}
else if(t[p].r-t[p].l>1)
{
t[p].clen=t[ls].clen+t[rs].clen;
t[p].num=t[ls].num+t[rs].num-(t[ls].rcov&t[rs].lcov);
t[p].lcov=t[ls].lcov;t[p].rcov=t[rs].rcov;
}
else
{
t[p].clen=t[p].num=0;
t[p].lcov=t[p].rcov=0;
}
}
void insert(int p,int l,int r,int detal)
{
if(t[p].l==l&&t[p].r==r)
{
t[p].cov+=detal;
pushup(p); return;
}
if(r<=mid) insert(ls,l,r,detal);
else if(l>=mid) insert(rs,l,r,detal);
else
{
insert(ls,l,mid,detal);
insert(rs,mid,r,detal);
}
pushup(p);
}
int main()
{
//
freopen("test.txt","r",stdin);
scanf("%d",&N);
int cnt=0;
for(int i=0;i<N;i++)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
y1+=M; y2+=M;
line[cnt].x=x1;line[cnt].y1=y1;line[cnt].y2=y2;line[cnt++].f=1;
line[cnt].x=x2;line[cnt].y1=y1;line[cnt].y2=y2;line[cnt++].f=-1;
}
sort(line,line+cnt,cmp);
maketree(1,0,2*M);
int par=0,ans=0;
for(int i=0;i<cnt;i++)
{
int y1=line[i].y1,y2=line[i].y2;
insert(1,y1,y2,line[i].f);
if(i<cnt-1) ans+=t[1].num*2*(line[i+1].x-line[i].x);
ans+=abs(t[1].clen-par);
par=t[1].clen;
}
printf("%dn",ans);
return 0;
}

最后

以上就是怕孤独楼房为你收集整理的poj 1177 经典线段树+扫描线就周长并的全部内容，希望文章能够帮你解决poj 1177 经典线段树+扫描线就周长并所遇到的程序开发问题。

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