当前位置 : 首页 » 博文聚焦 » 正文

hdu 1828 poj 1177 picture 求周长并

分类 : 博文聚焦 | 发布时间 : 2012-01-27 22:30:00 | 浏览 : 0

需要记录上一次总的区间长度,和这一次的差的绝对值是x轴的增长量,

再记录这段区间内共有几段子区间即可算出y轴的增长量

同时要增加两个域lbd rbd(布尔型) 分别记录当前区间最左与最右的元素是否被覆盖

View Code
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 22222;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
struct seg{
double l,r,h;
int flag;
seg(){}
seg(double _l,double _r,double _h,int _flag):l(_l),r(_r),h(_h),flag(_flag){}
bool operator < (const seg &cmp) const{
return h<cmp.h;
}
}horizontal_seg[maxn];
int cover[maxn<<2];
bool lbd[maxn<<2],rbd[maxn<<2];
int num[maxn<<2];
double sum[maxn<<2],x[maxn];
void pushup(int rt,int l,int r){
if(cover[rt]){
lbd[rt]=rbd[rt]=true;
sum[rt]=x[r+1]-x[l];
num[rt]=1;
return ;
}
if(l==r){
num[rt]=lbd[rt]=rbd[rt]=sum[rt]=0;
return ;
}
lbd[rt]=lbd[rt<<1];
rbd[rt]=rbd[rt<<1|1];
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
num[rt]=num[rt<<1]+num[rt<<1|1];
if(lbd[rt<<1|1]&&rbd[rt<<1]) num[rt]--;
}
void update(int L,int R,int c,int l,int r,int rt){
if(L<=l&&r<=R){
cover[rt]+=c;
pushup(rt,l,r);
return ;
}
int m=(l+r)>>1;
if(L<=m) update(L,R,c,lson);
if(R>m) update(L,R,c,rson);
pushup(rt,l,r);
}
void init(){
memset(sum,0,sizeof(sum));
memset(cover,0,sizeof(cover));
memset(num,0,sizeof(num));
memset(lbd,false,sizeof(lbd));
memset(rbd,false,sizeof(rbd));
}
int main(){
int n,i,j,tot;
double x1,x2,y1,y2;
while(scanf("%d",&n)!=EOF){
tot=0;
for(i=1;i<=n;i++){
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
x[tot]=x1;
horizontal_seg[tot++]=seg(x1,x2,y1,1);
x[tot]=x2;
horizontal_seg[tot++]=seg(x1,x2,y2,-1);
}
sort(x,x+tot);
sort(horizontal_seg,horizontal_seg+tot);
int real_tot=unique(x,x+tot)-x;
init();
double pre=0,ans=0;
for(i=0;i<tot;i++){
int left=lower_bound(x,x+real_tot,horizontal_seg[i].l)-x;
int right=lower_bound(x,x+real_tot,horizontal_seg[i].r)-x-1;
update(left,right,horizontal_seg[i].flag,0,real_tot-1,1);
ans+=fabs(sum[1]-pre);
ans+=2*num[1]*(horizontal_seg[i+1].h-horizontal_seg[i].h);
pre=sum[1];
}
printf("%.0lf\n",ans);
}
return 0;
}

 

相关阅读: