Picture 线段树 扫描线 Usaco

传送门
很裸的扫描线
0. 写在前面 对于 这类题 ，他们常有十分显著的特征基本上就是几个简单图形进行覆盖然 后统计周长或者面积，有的会利用“扫描”特点一些奇怪东西然而这也往存在

扫描线求面积
要直接统计一个图形的面积显然暴力求解复杂度实在是太 高，这时我们需要对其进行优化我们这时假设有一条扫描线，从下向上进行如图显然整个形的面积可以用 分割成的几个矩形面积加和来求解，而中间高度可以直接利用 Y2 -Y1 算出，那么我们其实只需要维护有多少条线段被覆盖即可

利用线段树的区间修改加以维护

扫描线求周长
其实这就和之前的东西一样了，只是需要横竖扫两遍。

值得注意的是，因为一条入边必然对应着一条出边，因而不需要lazy只需要维护一个覆盖数即可
其次 入边要排在出边得前面，才能保证前面的优化正确

下面是代码，我写的比较麻烦，是求周长的，稍微改一下就变成了求面积的，本类题其实常伴随着离散化等操作

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define N 40000+5
#define M 80000+5
using namespace std;
int ans,n;
struct data
{
int l,r,c,m;
int lazy;
data () {}
}tr[M];
inline int read()
{
int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
struct ROW
{
int y1,y2;
int x;
int in;
bool operator < (const ROW &z)const
{
return x^z.x?x<z.x:in<z.in;
}
void output(int i)
{
printf("ROW[%d] x=%d %d %dn",i,x-40,y1-40,y2 -40);
}
}r[N];
struct LINE
{
int y;
int x1,x2;
int in;
bool operator < (const LINE &z)const
{
return y^z.y?y<z.y:in<z.in;
}
void output(int i)
{
printf("ROW[%d] y=%d %d %dn",i,y-40,x1-40,x2-40 );
}
}l[N];
void build(int k,int l,int r)
{
tr[k].l=l,tr[k].r=r;
if(l==r)
{
tr[k].lazy=tr[k].m=tr[k].c=0;return;}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
tr[k].lazy=tr[k].m=tr[k].c=0;
}
int CCC = 0;
void updata(int k)
{
if(tr[k].l==tr[k].r)
{
if(tr[k].c)
tr[k].m=1;
else
tr[k].m=0;
return ;
}
if(tr[k].c)
tr[k].m=tr[k].r-tr[k].l+1;
else
tr[k].m=tr[k<<1].m+tr[k<<1|1].m;
//if(!tr[k].c)
//
tr[k].c=min(tr[k<<1].c,tr[k<<1|1].c);
return ;
}
void down(int k)
{
int tmp=tr[k].lazy;
tr[k<<1].lazy+=tmp;
tr[k<<1].c+=tmp;
updata(k<<1);
tr[k<<1|1].lazy+=tmp;
tr[k<<1|1].c+=tmp;
updata(k<<1|1);
tr[k].lazy=0;
return;
}
void change(int k,int l,int r,int x)
{
if(l==tr[k].l && r==tr[k].r)
{
//tr[k].lazy+=x;
tr[k].c+=x;
updata(k);
if(CCC <= 3)
{
printf("k=%d
lazy=%d
c=%d
m=%d
tl=%d
tr=%d
l=%d
r=%dn", k, tr[k].lazy, tr[k].c,
tr[k].m, tr[k].l-40, tr[k].r-40, l-40, r-40);
}
return ;
}
//if(tr[k].lazy)
//
down(k);
int mid=(tr[k].l+tr[k].r)>>1;
if(r<=mid)
change(k<<1,l,r,x);
else if(l>mid)
change(k<<1|1,l,r,x);
else
{
change(k<<1,l,mid,x);
change(k<<1|1,mid+1,r,x);
}
updata(k);
if(CCC <= 3)
{
printf("2 k=%d
lazy=%d
c=%d
m=%d
tl=%d
tr=%d
l=%d
r=%dn", k, tr[k].lazy, tr[k].c,
tr[k].m, tr[k].l-40, tr[k].r-40, l-40, r-40);
}
}
/*int ask(int k,int l,int r)
{
if(l==tr[k].l && r==tr[k].r)
return tr[k].m;
if(tr[k].lazy)
down(k);
int mid=(tr[k].r+tr[k].l)>>1;
if(r<=mid)
return ask(k<<1,l,r);
else if(l>mid)
return ask(k<<1|1,l,r);
return ask(k<<1,l,mid)+ask(k<<1,mid+1,r);
}*/
void add(int x1,int y1,int x2,int y2)
{
static int cnt=0;
r[++cnt].x=x1,r[cnt].y1=y1,r[cnt].y2=y2;
r[cnt].in=0;
l[cnt].y=y1,l[cnt].x1=x1,l[cnt].x2=x2;
l[cnt].in=0;
r[++cnt].x=x2,r[cnt].y1=y1,r[cnt].y2=y2;
r[cnt].in=1;
l[cnt].y=y2,l[cnt].x1=x1,l[cnt].x2=x2;
l[cnt].in=1;
return ;
}
void out()
{
for(int i=1;i<=200;++i)
{
printf("%d %d %d %dn",tr[i].l,tr[i].r,tr[i].c,tr[i].m);
}
return ;
}
int main()
{
//freopen("seg.in", "r", stdin);
//freopen("tt.out", "w", stdout);
cin>>n;
for(int i=1,x1,x2,y1,y2;i<=n;++i)
{
x1=read()+10001,y1=read()+10001,x2=read()+10001,y2=read()+10001;
add(x1,y1,x2,y2);
}
sort(l+1,l+2*n+1);
sort(r+1,r+2*n+1);
build(1,1,20002);
int tmp=0;
for(int i=1;i<=2*n;++i)
{
CCC=4;
if(!l[i].in)
change(1,l[i].x1,l[i].x2-1,1);
else
change(1,l[i].x1,l[i].x2-1,-1);
int ss=tr[1].m;
//printf("pre=%d
now=%d
+=%dn", tmp, ss, abs(ss-tmp) );
ans+=abs(ss-tmp);
tmp=ss;
//out();
}
//printf("%dn",ans );
build(1,1,20002);
tmp=0;
for(int i=1;i<=2*n;++i)
{
if(!r[i].in)
change(1,r[i].y1,r[i].y2-1,1);
else
change(1,r[i].y1,r[i].y2-1,-1);
int ss=tr[1].m;
//printf("pre=%d
now=%d
+=%dn", tmp, ss, abs(ss-tmp) );
ans+=abs(ss-tmp);
tmp=ss;
}
cout<<ans;
}

最后

以上就是高大镜子为你收集整理的Picture 线段树 扫描线 Usaco的全部内容，希望文章能够帮你解决Picture 线段树 扫描线 Usaco所遇到的程序开发问题。

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