[poj1151]Atlantis & [poj1177]picture（扫描线）

50 阅读 0 评论 33 点赞

我是靠谱客的博主微笑小伙，最近开发中收集的这篇文章主要介绍[poj1151]Atlantis & [poj1177]picture（扫描线），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

玩一玩扫描线，这个东西还是很强力的，而且容易yy。但是就是细节很多，所以查错特别麻烦。
推荐这篇blog: https://www.cnblogs.com/yangsongyi/p/8378629.html

【poj1151】
http://poj.org/problem?id=1151
题意：
在平面直角坐标系上有一些矩形，他们可能会互相重叠，求矩阵的并（也就是所有矩阵覆盖的部分）的面积。譬如说：
在这里插入图片描述
有色的面积就是所求。

扫描线模板题。
离散y坐标，以y坐标建立线段树跑扫描线。排序x，每次去差值乘上线段树根节点所维护扫描线长度即算出面积进入答案中。
在线段树中维护一个cnt和一个len，len表示当前线段树节点所维护的扫描线长度，cnt表示当前线段树所维护区间的重叠情况，辅助维护len（知道什么时候更新）。进来一条线就给维护这条线的线段树节点的cnt+1。向上更新的时候，当一个节点的cnt>0的时候就更新他的长度，否则他的长度等于他左右儿子的长度和。具体可以模拟一下过程。

注意扫描线的建树和普通线段树不同。扫描线的线段树维护的是点，所以我们在分左右孩子建树时的区间时(l,mid)和(mid,r)而不是像之前那样打(mid+1,r)。如果打(mid+1,r)的会维护不到(mid,mid+1)的点。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MX=1e5+10;
const int N=3e2+10;
struct seg
{
double l,r;
int cnt;
double len;
}tr[N*4];
int n;
struct node
{
double x,y1,y2;
int flag;
}p[N*2];
bool cmp(node a,node b){return a.x<b.x;}
double b[N*2];
void push_up(int now)
{
if(tr[now].cnt>0)
tr[now].len=tr[now].r-tr[now].l;
else
tr[now].len=tr[now*2].len+tr[now*2+1].len;
}
void build(int now,int l,int r)
{
tr[now].l=b[l]; tr[now].r=b[r];
if(l>=r-1){tr[now].len=0;return;}//debug:特判r=l+1的情况 
if(l<r+1) //debug:如果r=l+1的话,mid会一直等于l进入死循环 
{
int mid=(l+r)/2,lc=now*2,rc=now*2+1;
build(lc,l,mid);
build(rc,mid,r);//debug:扫描线维护点所以mid不+1 
push_up(now);
}
}
void change(int now,double y1,double y2,int flag)
{
if(tr[now].l==y1 && tr[now].r==y2)
{
tr[now].cnt+=flag;
push_up(now);
return;
}
int lc=now*2,rc=now*2+1;
if(tr[lc].r>y1)
change(lc,y1,min(tr[lc].r,y2),flag);
if(tr[rc].l<y2)
change(rc,max(tr[rc].l,y1),y2,flag);
push_up(now);
}
int main()
{
int ti=0;
double x1,y1,x2,y2,ans;
while(scanf("%d",&n)&&n)
{
ans=0;
memset(b,0,sizeof(b));
for(int i=1;i<=n;i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
p[i].x=x1; p[i].y1=y1; p[i].y2=y2; p[i].flag=1;
p[i+n].x=x2; p[i+n].y1=y1; p[i+n].y2=y2; p[i+n].flag=-1;
b[i]=y1; b[i+n]=y2;
}
sort(b+1,b+2*n+1);
sort(p+1,p+2*n+1,cmp);
for(int i=1;i<4*N;i++) tr[i].cnt=tr[i].len=0;
build(1,1,2*n);
change(1,p[1].y1,p[1].y2,p[1].flag);
for(int i=2;i<=2*n;i++)
{
ans+=(p[i].x-p[i-1].x) * tr[1].len;
change(1,p[i].y1,p[i].y2,p[i].flag);
}
printf("Test case #%dnTotal explored area: %.2lfnn",++ti,ans);
}
return 0;
}

【poj1177】Picture
http://poj.org/problem?id=1177
题意：
在平面直角坐标系上有一些矩形，他们可能会互相重叠，求矩阵的并（也就是所有矩阵覆盖的部分）的周长。譬如说：
在这里插入图片描述
红色部分的长度即为所求。

同样离散化y坐标建立线段树跑扫描线，同时按照x排序。
我们发现对于竖线我们可以参照上一题的维护方法维护一个cnt和len，在每次进来一条新的竖线之后change进线段树后给答案加上（abs(上次的答案 - 现在根节点所维护扫描线长度)）即可。

但是对于横线应该如何办呢？我们考虑什么时候要计算横线，只有当两条竖线分开的时候，中间才会拉出来横线。那么我们可以维护一个num，表示当前节点下的连续线段有多少个。也就是说，如果一个节点下面维护了(1,3),(4,5),(5,6)三条线段，那么num=2，因为(4,5)(5,6)是连续的，他们两个只会拉出来两条横线。那么为了维护他，我们在cnt的基础上需要维护一个lp,rp表示线段的两端有没有被覆盖.
当当前节点的cnt>0时，num=1,cnt如果左孩子的rp=1.
当前cnt=0时，当前节点的num=左右孩子的num和，但是如果右孩子的lp=1那就说明中间重复了，那么当前节点的num就要-1。

维护了num就可以计算横线的值了，每次进来一个扫描线，我们把横坐标和上一个作差得出这一段要加的几条横线的长度，然后根节点的num值*2（因为有上下两条边）就是当前要加的横线的数量，乘起来计入答案即可。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e4+10;
struct seg
{
double l,r;
int cnt,num;//num 线段树中连续的线段有多少条 
double len;
int lp,rp;//lp
rp记录这一个节点的两个端点是不是已经覆盖 来维护num 
}tr[N*4];
int n;
struct node
{
double x,y1,y2;
int flag;
}p[N*2];
bool cmp(node a,node b){return a.x<b.x;}
double b[N*2];
void push_up(int now)
{
if(tr[now].cnt>0)
{
tr[now].lp=tr[now].rp=1;
tr[now].num=1;
tr[now].len=tr[now].r-tr[now].l;
}
else
{
int lc=now*2,rc=now*2+1;
tr[now].len=tr[lc].len+tr[rc].len;
tr[now].num=tr[lc].num+tr[rc].num;
tr[now].lp=tr[lc].lp; tr[now].rp=tr[rc].rp;
if(tr[lc].rp && tr[rc].lp) tr[now].num--;
//debug 如果左节点的rp与右节点的lp都是1，那么父节点的num值减去1
}
}
void build(int now,int l,int r)
{
tr[now].l=b[l]; tr[now].r=b[r];
tr[now].lp=tr[now].rp=0;
if(l>=r-1){tr[now].num=tr[now].len=tr[now].cnt=0; return;}
if(l<r+1)
{
int mid=(l+r)/2,lc=now*2,rc=now*2+1;
build(lc,l,mid);
build(rc,mid,r);
push_up(now);
}
}
void change(int now,double y1,double y2,int p)
{
if(tr[now].l==y1 && tr[now].r==y2)
{
tr[now].cnt+=p;
push_up(now);
return;
}
int lc=now*2,rc=now*2+1;
if(tr[lc].r>y1)
change(lc,y1,min(tr[lc].r,y2),p);
if(tr[rc].l<y2)// debug 不打else 两个都可以进行 
change(rc,max(tr[rc].l,y1),y2,p);
push_up(now);
}
int main()
{
int n;
while(~scanf("%d",&n))
{
double x1,y1,x2,y2;
memset(b,0,sizeof(b));
for(int i=1;i<=n;i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
p[i].x=x1; p[i].y1=y1; p[i].y2=y2; p[i].flag=1;
p[i+n].x=x2; p[i+n].y1=y1; p[i+n].y2=y2; p[i+n].flag=-1;
b[i]=y1; b[i+n]=y2;
}
sort(b+1,b+2*n+1);
int m=unique(b+1,b+2*n+1)-(b+1);
build(1,1,m);
sort(p+1,p+2*n+1,cmp);
double ans=0,last=0;
change(1,p[1].y1,p[1].y2,p[1].flag);
ans+=fabs(last-tr[1].len);
last=tr[1].len;
for(int i=2;i<=2*n;i++)
{
ans+=(p[i].x-p[i-1].x)*tr[1].num*2;//横线 
change(1,p[i].y1,p[i].y2,p[i].flag);
ans+=fabs(last-tr[1].len);	//竖线 
last=tr[1].len;
}
printf("%.0lfn",ans);
}
return 0;
}