【POJ 1389】Area of Simple Polygons(线段树+扫描线,矩形并面积)

离散化后,[1,10]=[1,3]+[6,10]就丢了[4,5]这一段了。

因为更新[3,6]时,它只更新到[3,3],[6,6]。

要么在相差大于1的两点间加入一个值,要么就让左右端点为l,r的线段树节点表示到x[l]到x[r+1]的区间。

这样tree[l,r]=tree[l,m]+tree[m+1,r]=[x[l],x[m+1]]+[x[m+1],x[r+1]]

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define ll long long
#define N 2005
using namespace std;
struct P{ll s,e,h,f;}p[N];
struct Tree{ll sum,c;}t[N<<];
int x[N],n,m,ans;
int cmp(const P &a,const P &b){
return a.h<b.h;
}
void init(){
n=m=ans=;
memset(p,,sizeof p);
memset(t,,sizeof t);
x[]=-;
}
void pushUp(ll rt,ll l,ll r){
if(t[rt].c)t[rt].sum=x[r+]-x[l];
else if(l==r)t[rt].sum=;
else t[rt].sum=t[rt<<].sum+t[rt<<|].sum;
}
void update(ll s,ll e,ll rt,ll l,ll r,ll v){
if(s<=l&&r<=e) t[rt].c+=v;
else {
if(l>e||r<s)return;
ll m=l+r>>;
update(s,e,rt<<,l,m,v);
update(s,e,rt<<|,m+,r,v);
}
pushUp(rt,l,r);
}
int main()
{
int a,b,c,d;
init();
while(cin>>a>>b>>c>>d){
if(a<)break;
while(a>=){
p[++n].s=a,p[n].e=c,p[n].h=b,p[n].f=;x[n]=a;
p[++n].s=a,p[n].e=c,p[n].h=d,p[n].f=-;x[n]=c;
cin>>a>>b>>c>>d;
}
sort(x+,x++n);
for(int i=;i<=n;i++)
if(x[i]!=x[i-])x[++m]=x[i]; sort(p+,p++n,cmp);
for(int i=;i<n;i++){
int l=lower_bound(x,x+m,p[i].s)-x;
int r=lower_bound(x,x+m,p[i].e)-x-; update(l,r,,,m,p[i].f);
ans+=t[].sum*(p[i+].h-p[i].h);
}
cout<<ans<<endl;
init();
}
return ;
}
  
上一篇:Git的原理简介和常用命令


下一篇:Git详解之九 Git内部原理