poj1177--Picture--扫描线

思想和前段时间的1151差不多，

都是通过扫描线的移动来计算周长，不同的是要通过对与x轴平行的扫描线扫一次，与y轴平行的扫描线扫一次，

扫描两次得到周长。

变量last为记录上一次扫描得到的长度，sum为记录这一次总共扫描得到的长度。

abs(sum-last)即为所扫描到的一次长度，

非常耐人寻味的是，我询问学长为什么可以这样做的时候，学长提到了一个投影的概念，即投影的变化反应长度的变化，

智商拙计。。。。还在思考ing。

据说这道题还可以通过一次扫描顺带扫描y轴得到周长（记录x轴上分割开来的即不连续线段个数，乘以2就是y的个数。PS：这个有种特殊情况不满足，即一个矩形包含一个小矩形的情况），改天再碰扫描线的时候再来看看吧。

一下是代码：可与poj1151比较，是我的代码风格= =！

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxnum=10010;
typedef struct
{
int l,r;
int ll,rr;
int cover;
int len;
}Nodex;
typedef struct
{
int h,d;
int hh,dd;
int cover;
int len;
}Nodey;
typedef struct
{
int flag; //记录出边还是入边,入边为1，出边为-1.
int x1,x2,y;
}scanlen_x;
typedef struct
{
int flag; //记录出边还是入边,入边为1，出边为-1
int y1,y2,x;
}scanlen_y;
Nodex treex[maxnum*4];
Nodey treey[maxnum*4];
scanlen_x scanx[maxnum];
scanlen_y scany[maxnum];
int x[maxnum];
int y[maxnum];
bool mycomparex(scanlen_x a,scanlen_x b)
{
return a.y<b.y;
}
bool mycomparey(scanlen_y a,scanlen_y b)
{
return a.x<b.x;
}
void buildx(int root,int l,int r)
{
treex[root].l=l;
treex[root].r=r;
treex[root].ll=x[l];
treex[root].rr=x[r];
treex[root].cover=0;
treex[root].len=0;
if(l+1==r) return;
int mid=(l+r)>>1;
buildx(root<<1,l,mid);
buildx(root<<1|1,mid,r);
}
void buildy(int root,int l,int r)
{
treey[root].d=l;
treey[root].h=r;
treey[root].dd=y[l];
treey[root].hh=y[r];
treey[root].cover=0;
treey[root].len=0;
if(l+1==r) return;
int mid=(l+r)>>1;
buildy(root<<1,l,mid);
buildy(root<<1|1,mid,r);
}
void updatex(scanlen_x a,int l,int r,int root)
{
if(l==treex[root].ll&&r==treex[root].rr)
treex[root].cover+=a.flag;
else
{
int mid=(treex[root].l+treex[root].r)>>1;
if(l>=x[mid]) updatex(a,l,r,root<<1|1);
else if(r<=x[mid]) updatex(a,l,r,root<<1);
else
{
updatex(a,l,x[mid],root<<1);
updatex(a,x[mid],r,root<<1|1);
}
}
if(treex[root].cover)//以下更新root的len，即扫描到的总长度
treex[root].len=treex[root].rr-treex[root].ll;
else if(treex[root].l+1==treex[root].r)
treex[root].len=0;
else
treex[root].len=treex[root<<1].len+treex[root<<1|1].len;
}
void updatey(scanlen_y a,int d,int h,int root)
{
if(d==treey[root].dd&&h==treey[root].hh)
treey[root].cover+=a.flag;
else
{
int mid=(treey[root].d+treey[root].h)>>1;
if(d>=y[mid]) updatey(a,d,h,root<<1|1);
else if(h<=y[mid]) updatey(a,d,h,root<<1);
else
{
updatey(a,d,y[mid],root<<1);
updatey(a,y[mid],h,root<<1|1);
}
}//以下更新root的len，即扫描到的总长度.
if(treey[root].cover)
treey[root].len=treey[root].hh-treey[root].dd;
else if(treey[root].d+1==treey[root].h)
treey[root].len=0;
else
treey[root].len=treey[root<<1].len+treey[root<<1|1].len;
}
int main()
{
int n;
while(scanf("%d",&n)==1)
{
int i,m=1,k=1;
for(i=1;i<=n;++i)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
scanx[m].x1=x1;scanx[m].x2=x2;scanx[m].y=y1;scanx[m].flag=1;
x[m++]=x1;
scanx[m].x1=x1;scanx[m].x2=x2;scanx[m].y=y2;scanx[m].flag=-1;
x[m++]=x2;
scany[k].y1=y1;scany[k].y2=y2;scany[k].x=x1;scany[k].flag=1;
y[k++]=y1;
scany[k].y1=y1;scany[k].y2=y2;scany[k].x=x2;scany[k].flag=-1;
y[k++]=y2;
}
--m,--k;
sort(scanx+1,scanx+m+1,mycomparex);
sort(x+1,x+m+1);
sort(scany+1,scany+k+1,mycomparey);
sort(y+1,y+k+1);
int o=2,p=2;
for(i=2;i<=m;++i)
if(x[i]!=x[i-1]) x[o++]=x[i];
for(i=2;i<=k;++i)
if(y[i]!=y[i-1]) y[p++]=y[i];
--o,--p;
buildx(1,1,o);//在x轴建立线段树
buildy(1,1,p);//在y轴建立线段树
int ans=0,last=0;
for(i=1;i<=m;++i)
{
updatex(scanx[i],scanx[i].x1,scanx[i].x2,1);
ans+=abs(treex[1].len-last);
last=treex[1].len;
}
last=0;
for(i=1;i<=k;++i)
{
updatey(scany[i],scany[i].y1,scany[i].y2,1);
ans+=abs(treey[1].len-last);
last=treey[1].len;
}
printf("%dn",ans);
}
return 0;
}

最后

以上就是伶俐小鸽子为你收集整理的poj1177--Picture--扫描线的全部内容，希望文章能够帮你解决poj1177--Picture--扫描线所遇到的程序开发问题。

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