[离散化+线段树+扫描线]POJ_2091_Picture

题意：求矩形周长并。

总结：这道题也算是很经典的一道扫描线题吧，就是陈宏论文上面提到的那道IOI的试题，也算试了一下用扫描线法求矩形的周长并.

注意点：1.几个必须要的域，cnt-区间被线段覆盖的次数，sum-测度，seq-连续段数，lbd-是否包含区间的左边界，rbd-是否包含区间的右边界，其中lbd,rbd是为了求得seq的。

2.理解线段插入删除的思想。//为什么在这里不需要把信息传给子节点，这里需要进一步理解。

3.理解如果更新上述的几个域.

4.如何根据测度信息和连续段数信息计算答案。//需要进一步理解

各种蛋疼：1.注意求X方向的周长与求Y方向的周长位于update的两侧。。（细想一下就知道了）

网上讲这个题的资料很多（强烈推荐1999年陈宏的国家集训队论文），不多说了，直接上代码。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN = 5555;
double sum[MAXN*6],x[MAXN*2];
int cnt[MAXN*6],rbd[MAXN*6],lbd[MAXN*6],seq[MAXN*6],n,num_x,line_num;
struct Line{
double l,r,h;
int s;
Line(){}
Line(double ll,double rr,double hh,int ss):l(ll),r(rr),h(hh),s(ss){}
bool operator < (const Line &l) const{
return h<l.h;
}
}L[MAXN*2];
#define lson l,m,rt<<1
#define rson m,r,rt<<1|1
void pushUP(int l,int r,int rt){
if(cnt[rt]){
sum[rt] = x[r]-x[l];
seq[rt] = lbd[rt] = rbd[rt] = 1;
}else{
sum[rt] = sum[rt<<1]+sum[rt<<1|1];
seq[rt] = seq[rt<<1]+seq[rt<<1|1]-rbd[rt<<1]*lbd[rt<<1|1];
rbd[rt] = rbd[rt<<1|1];
lbd[rt] = lbd[rt<<1];
}
}
void update(int L,int R,int s,int l,int r,int rt){
if(L<=l&&R>=r){
cnt[rt]+=s;
pushUP(l,r,rt);
//cout<<l<<" "<<r<<" "<<seq[rt]<<" "<<lbd[rt]<<" "<<rbd[rt]<<endl;system("pause");
return;
}
int m = (l+r)>>1;
if(m>L)update(L,R,s,lson);
if(m<R)update(L,R,s,rson);
pushUP(l,r,rt);
//cout<<l<<" "<<r<<" "<<seq[rt]<<" "<<lbd[rt]<<" "<<rbd[rt]<<endl;system("pause");
}
int search(double k){
int l=0,r=num_x-1,m;
while(l<=r){
m = (l+r)>>1;
if(x[m]==k)return m;
else if(k<x[m])r=m-1;
else l=m+1;
}
return -1;
}
int main(){
while(scanf("%d",&n)!=EOF){
num_x = line_num = 0;
for(int i=0;i<n;i++){
double a,b,c,d;
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
x[num_x++] = a;
x[num_x++] = c;
L[line_num++] = Line(a,c,b,1);
L[line_num++] = Line(a,c,d,-1);
}
sort(L,L+line_num);sort(x,x+num_x);
int temp = 1;
for(int i=1;i<num_x;i++)if(x[i]!=x[i-1])x[temp++]=x[i];
num_x = temp;
memset(cnt,0,sizeof(cnt));
memset(sum,0,sizeof(sum));
memset(seq,0,sizeof(seq));
memset(lbd,0,sizeof(lbd));
memset(rbd,0,sizeof(rbd));
double ans = 0,preM = 0;
for(int i=0;i<line_num;i++){
int l = search(L[i].l);
int r = search(L[i].r);
if(i)ans += 2*seq[1]*(L[i].h-L[i-1].h);
update(l,r,L[i].s,0,num_x-1,1);
//cout<<l<<" "<<r<<" "<<L[i].h<<" "<<L[i].s<<endl;
//cout<<sum[1]<<" "<<seq[1]<<" "<<lbd[1]<<" "<<rbd[1]<<endl;
ans += fabs(sum[1]-preM);
preM = sum[1];
}
printf("%.0lfn",ans);
}
return 0;
}

最后

以上就是悲凉橘子为你收集整理的[离散化+线段树+扫描线]POJ_2091_Picture的全部内容，希望文章能够帮你解决[离散化+线段树+扫描线]POJ_2091_Picture所遇到的程序开发问题。

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