poj1177 矩形周长并

线段树扫描线的模板题,一个月前写的发现忘了一些还是要看看以前的博客呀!

/*
思路:数据小不用离散化处理,线段树叶子结点维护一个区间
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 20005
struct Seg{
int l,r,h,s;
Seg(){}
Seg(int a,int b,int c,int d):l(a),r(b),h(c),s(d){}
bool operator<(const Seg & a)const {
//if(h==a.h) return s>a.s;
return h<a.h;
}
}ss[maxn];
bool lbd[maxn<<],rbd[maxn<<];//被覆盖的区域是否和左右区间线重合
int numseg[maxn<<],cnt[maxn<<],len[maxn<<];
void pushup(int rt,int l,int r){
if(cnt[rt]){
lbd[rt]=rbd[rt]=;
len[rt]=r-l;
numseg[rt]=;
}
else if(l+==r)
len[rt]=numseg[rt]=rbd[rt]=lbd[rt]=;
else {
lbd[rt]=lbd[rt<<];
rbd[rt]=rbd[rt<<|];
len[rt]=len[rt<<]+len[rt<<|];
numseg[rt]=numseg[rt<<]+numseg[rt<<|];
if(lbd[rt<<|] && rbd[rt<<]) numseg[rt]-=;
}
}
#define lson l,m,rt<<1
#define rson m,r,rt<<1|1
void update(int L,int R,int c,int l,int r,int rt){
if(L<=l && R>=r){
cnt[rt]+=c;
pushup(rt,l,r);
return;
}
int m=l+r>>;
if(L<m) update(L,R,c,lson);
if(R>m) update(L,R,c,rson);
pushup(rt,l,r);
}
void init(){
memset(lbd,,sizeof lbd);
memset(rbd,,sizeof rbd);
memset(cnt,,sizeof cnt);
memset(len,,sizeof len);
memset(numseg,,sizeof numseg);
}
int main(){
int n;
while(scanf("%d",&n)==){
init();
int m=,x1,y1,x2,y2,lbd=,rbd=-,last=,ans=;
for(int i=;i<=n;i++){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
ss[m++]=Seg(x1,x2,y1,);
ss[m++]=Seg(x1,x2,y2,-);
lbd=min(lbd,x1),rbd=max(rbd,x2);
}
sort(ss,ss+m);
for(int i=;i<m;i++){
update(ss[i].l,ss[i].r,ss[i].s,lbd,rbd,);
ans+=abs(len[]-last);last=len[];
ans+=numseg[]*(ss[i+].h-ss[i].h);
}
printf("%d\n",ans);
}
return ;
}
上一篇:C++ Primer的课后规划问题的第八章


下一篇:Swift自适应布局(Adaptive Layout)教程(二)