/**//*
Author:miyou
PROG:the perimeter of many rectangles
LANG:C++
*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MAXN 1000000
const __int64 mininf=1000000;
const __int64 maxinf=-1000000;
struct Line
{
__int64 count,len;//count 記錄線段覆蓋次數(shù),len 該段線段長(zhǎng)度
__int64 l,r;//線段左右兩端點(diǎn)
int lbc,rbc;//線段左右兩端點(diǎn)被覆蓋的次數(shù),0表示未被覆蓋
__int64 nseg;//該線段中連續(xù)線段個(gè)數(shù).
};
struct node
{
__int64 x,down,up;//掃描線,down 線的下端點(diǎn),up 線的上端點(diǎn),x掃描線的x位置
bool flag;//表示是矩形的左邊線還是右邊線
node(__int64 tx,__int64 td,__int64 tu,bool tf):x(tx),down(td),up(tu),flag(tf)
{
}
};
__int64 miny,maxy;
vector< node > vec;
Line Ltree[MAXN];
bool operator< (const node& a,const node& b)
{
return a.x<b.x;
}
void build(__int64 l,__int64 r,int step)
{
Ltree[step].count=0;Ltree[step].len=0;
Ltree[step].lbc=false;Ltree[step].rbc=false;
Ltree[step].nseg=0;
Ltree[step].r=r;Ltree[step].l=l;
if(r-l>1)
{
build(l,(l+r)/2,2*step);
build((l+r)/2,r,2*step+1);
}
}
void update(int step)
{
if(Ltree[step].count>0)
{
Ltree[step].len=Ltree[step].r-Ltree[step].l;
Ltree[step].nseg=1;
}
else
if(Ltree[step].r-Ltree[step].l>1)
{
Ltree[step].len=Ltree[2*step].len+Ltree[2*step+1].len;
Ltree[step].nseg=Ltree[2*step].nseg+Ltree[2*step+1].nseg;
if(Ltree[step].nseg&&Ltree[2*step].rbc&&Ltree[2*step+1].lbc)
Ltree[step].nseg--;
}
else
{
Ltree[step].len=0;
Ltree[step].nseg=0;
}
}
void insert(__int64 l,__int64 r,int step)
{
if(Ltree[step].l==l) Ltree[step].lbc++;
if(Ltree[step].r==r) Ltree[step].rbc++;
if(l==Ltree[step].l&&Ltree[step].r==r)
Ltree[step].count++;
else
{
__int64 mid=(Ltree[step].l+Ltree[step].r)/2;
if(r<=mid)
insert(l,r,2*step);
else
if(l>=mid)
insert(l,r,2*step+1);
else
{
insert(l,mid,2*step);
insert(mid,r,2*step+1);
}
}
update(step);
}
void del(__int64 l,__int64 r,int step)
{
if(Ltree[step].l==l) Ltree[step].lbc--;
if(Ltree[step].r==r) Ltree[step].rbc--;
if(l==Ltree[step].l&&Ltree[step].r==r)
Ltree[step].count--;
else
{
__int64 mid=(Ltree[step].l+Ltree[step].r)/2;
if(r<=mid)
del(l,r,2*step);
else
if(l>=mid)
del(l,r,2*step+1);
else
{
del(l,mid,2*step);
del(mid,r,2*step+1);
}
}
update(step);
}
int main()
{
int n;
__int64 x1,x2,y1,y2;
while(scanf("%d",&n)==1)
{
miny=mininf;
maxy=maxinf;
for(int i=0;i<n;i++)
{
scanf("%I64d%I64d%I64d%I64d",&x1,&y1,&x2,&y2);
vec.push_back(node(x1,y1,y2,true));
vec.push_back(node(x2,y1,y2,false));
miny=min(miny,y1);
maxy=max(maxy,y2);
}
sort(vec.begin(),vec.end());
//cout<<miny<<" "<<maxy<<endl;
build(miny,maxy,1);
__int64 peri=0;
int m=vec.size();
__int64 lastlen=0,lastseg=0;
for(int i=0;i<m;i++)
{
if(vec[i].flag)
insert(vec[i].down,vec[i].up,1);
else
del(vec[i].down,vec[i].up,1);
peri+=abs(Ltree[1].len-lastlen);
//cout<<"len:"<<Ltree[1].len<<endl;
lastlen=Ltree[1].len;
if(i)
peri+=2*(vec[i].x-vec[i-1].x)*lastseg;
lastseg=Ltree[1].nseg;
//cout<<"seg:"<<Ltree[1].nseg<<endl;
}
printf("%I64d\n",peri);
}
return 0;
}
posted on 2009-05-03 21:02
米游 閱讀(772)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
ACM