POJ-1177 Picture

线段树+扫描线+离散化

扫描线是用于求解矩形覆盖面积或者矩形并轮廓长度的算法，一般都是搭配线段树使用

再加上离散化，可以把时间优化到最少

附上一个讲扫描线挺详细的链接：https://blog.csdn.net/qq_38786088/article/details/78633478

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=10000+10;
struct line
{
int x,y1,y2;
int f;
bool operator < (const line &u) const
{
return x<u.x;
}
}edge[maxn];
int l[maxn<<2],r[maxn<<2],len[maxn<<2],sum[maxn<<2],lbt[maxn<<2],rbt[maxn<<2],cover[maxn<<2];
int Y[maxn];
void build(int l,int r,int rt)
{
len[rt]=sum[rt]=lbt[rt]=rbt[rt]=cover[rt]=0;
if(r-l==1) return;
int m=(l+r+1)>>1;
build(l,m,rt<<1);
build(m,r,rt<<1|1);
}
void PushUp(int rt,int l,int r)
{
if(cover[rt]>0)
{
len[rt]=Y[r]-Y[l];
lbt[rt]=rbt[rt]=1;
sum[rt]=1;
}
else if(r-l==1)
{
len[rt]=0;
lbt[rt]=rbt[rt]=0;
sum[rt]=0;
}
else
{
len[rt]=len[rt<<1]+len[rt<<1|1];
lbt[rt]=lbt[rt<<1];rbt[rt]=rbt[rt<<1|1];
sum[rt]=sum[rt<<1]+sum[rt<<1|1]-rbt[rt<<1]*lbt[rt<<1|1];
}
}
void update(int L,int R,int f,int l,int r,int rt)
{
if(L<=Y[l]&&R>=Y[r])
{
cover[rt]+=f;
}
else
{
int m=(l+r+1)>>1;
if(L<Y[m]) update(L,R,f,l,m,rt<<1);
if(R>Y[m]) update(L,R,f,m,r,rt<<1|1);
}
PushUp(rt,l,r);
}
int main()
{
//freopen("/home/zlwang/test.txt","r",stdin);
int n;
while(~scanf("%d",&n))
{
int x1,x2,y1,y2;
int cnt=0;
for(int i=0;i<n;i++)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
Y[i]=y1;
Y[n+i]=y2;
edge[cnt].y1=y1;
edge[cnt].y2=y2;
edge[cnt].x=x1;
edge[cnt].f=1;
cnt++;
edge[cnt].y1=y1;
edge[cnt].y2=y2;
edge[cnt].x=x2;
edge[cnt].f=-1;
cnt++;
}
sort(edge,edge+2*n);
sort(Y,Y+2*n);
cnt=1;
for(int i=1;i<2*n;i++)
if(Y[i]!=Y[i-1]) Y[cnt++]=Y[i];
build(0,cnt-1,1);
int ans=0,lastlen=0;
for(int i=0;i<2*n-1;i++)
{
update(edge[i].y1,edge[i].y2,edge[i].f,0,cnt-1,1);
ans+=2*sum[1]*(edge[i+1].x-edge[i].x);
ans+=fabs(len[1]-lastlen);
lastlen=len[1];
}
ans+=edge[2*n-1].y2-edge[2*n-1].y1;
printf("%dn",ans);
}
return 0;
}

最后

以上就是冷静乐曲为你收集整理的POJ-1177 Picture的全部内容，希望文章能够帮你解决POJ-1177 Picture所遇到的程序开发问题。

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