HDU - 1828(矩形周长并 扫描线算法 )

主题算法思想参考notonlysuccess算法；

自己写了一遍，有很多地方比较巧妙；

线段树维护的值为len（扫到当前线段时的所有覆盖的线段总长），sumseg（扫到当前线段时的所有覆盖的线段的端点总数目） 需另外两个辅助参数lbd，rbd来计算；

本代码风格并未采用下推标记线段树写法，更简洁；因为只使用len【1】和sumseg【1】；所以只向上维护即可；

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = 31111;
int sumseg[maxn<<2],col[maxn<<2],len[maxn<<2],lbd[maxn<<2],rbd[maxn<<2];
void build(int l,int r,int rt){
sumseg[rt]=len[rt]=col[rt]=lbd[rt]=rbd[rt]=0;
if(l==r) return ;
int m=(l+r)>>1;
build(lson);
build(rson);
}
void pushup(int l,int r,int rt){
if(col[rt]){
sumseg[rt]=2;
len[rt]=r-l+1;
lbd[rt]=l; rbd[rt]=r;
}
else if(l==r){
len[rt] = sumseg[rt]=0;
}
else{
len[rt] = len[rt<<1] + len[rt<<1|1];
sumseg[rt] = sumseg[rt<<1] +sumseg[rt<<1|1];
if(sumseg[rt<<1] && sumseg[rt<<1|1] && rbd[rt<<1]+1==lbd[rt<<1|1])
sumseg[rt]-=2;
lbd[rt]=lbd[rt<<1]; rbd[rt]=rbd[rt<<1|1];
}
}
int ql,qr,val;
void update(int l,int r,int rt){
if(ql<=l && r<=qr){
col[rt]+=val;
pushup(l,r,rt);
return ;
}
int m=(l + r)>>1;
if(ql<=m) update(lson);
if(qr> m) update(rson);
pushup(l,r,rt);
}
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int add = 10002;
int L=1,R=25000,n;
struct segment {
int l,r,x,flag;
segment(int a,int b,int c,int d):l(a),r(b),x(c),flag(d){}
bool operator < (const segment& rhs) const {
return x < rhs.x || x == rhs.x && flag > rhs.flag;
}
};
vector<segment> a;
int main()
{
while(scanf("%d",&n)==1){
a.clear();
for(int i=1;i<=n;i++){
int aa,b,c,d;
scanf("%d %d %d %d",&aa,&b,&c,&d);
aa+=add; b+=add; c+=add; d+=add;
a.push_back(segment(b,d,aa,1));
a.push_back(segment(b,d,c,-1));
}
sort(a.begin(),a.end());
build(L,R,1);
int ans=0,last=0;
for(int i=0;i<a.size();i++){
segment& seg = a[i];
ql = seg.l; qr = seg.r-1; val = seg.flag;
update(L,R,1);
ans += abs(len[1] - last);
last = len[1];
ans += sumseg[1]*(i==a.size()-1 ? 0: a[i+1].x-a[i].x);
}
printf("%dn",ans);
}
return 0;
}

最后

以上就是风趣唇膏为你收集整理的HDU - 1828(矩形周长并 扫描线算法 )的全部内容，希望文章能够帮你解决HDU - 1828(矩形周长并 扫描线算法 )所遇到的程序开发问题。

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