HDu 3265 Posters(走査線)
題意:いくつかの筋空の矩形を与えて、彼らの面積の和を要求します.1つの矩形を4つの矩形に分解すれば、直接前のものをカバーすることができます.
いくつか注意すべき点があり、答えはintを超えます.リーフノードに直接更新するとタイムアウトします.x 1<=x 3のため、1つのポイントのみが更新されます.
いくつか注意すべき点があり、答えはintを超えます.リーフノードに直接更新するとタイムアウトします.x 1<=x 3のため、1つのポイントのみが更新されます.
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=200005;
int y[N*2],d;
struct Line
{
int x,y1,y2,co;
void fun(int a,int b,int c,int d){x=a;y1=b;y2=c;co=d;}
}line[N*2];
struct node
{
int left,right,co;
int lf,rf,len;
int mid(){return left+(right-left)/2;}
};
struct Segtree
{
node tree[N*8];
void build(int left,int right,int r)
{
tree[r].left=left; tree[r].right=right;
tree[r].lf=y[left]; tree[r].rf=y[right];
tree[r].co=tree[r].len=0;
if(left+1<right)
{
int mid=tree[r].mid();
build(left,mid,r*2);
build(mid,right,r*2+1);
}
}
void updata(Line e,int r)
{
if(e.y1<=tree[r].lf&&tree[r].rf<=e.y2)
{
tree[r].co+=e.co;
calen(r);
}
else
{
if(tree[r].left+1==tree[r].right) return;
if(e.y1<tree[r*2].rf) updata(e,r*2);
if(e.y2>tree[r*2+1].lf) updata(e,r*2+1);
calen(r);
}
}
void calen(int r)
{
if(tree[r].co>0)
{
tree[r].len=tree[r].rf-tree[r].lf;
}
else
{
if(tree[r].left+1==tree[r].right){tree[r].len=0;return;} // 。
else tree[r].len=tree[r*2].len+tree[r*2+1].len;
}
}
}seg;
void add_line(int,int,int,int);
int deal(int);
bool cmp(const Line &e1,const Line &e2)
{
return e1.x<e2.x;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
if(n==0) break;
d=0;
for(int i=0;i<n;i++)
{
int x1,y1,x2,y2,x3,y3,x4,y4;
scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
add_line(x1,y1,x3,y2); add_line(x3,y1,x4,y3);
add_line(x3,y4,x4,y2); add_line(x4,y1,x2,y2);
}
int cnt=deal(d);
long long ans=0;
seg.build(0,cnt-1,1);
seg.updata(line[0],1);
for(int i=1;i<d;i++)
{
ans+=(1LL*seg.tree[1].len*(line[i].x-line[i-1].x));
seg.updata(line[i],1);
}
printf("%I64d
",ans);
}
return 0;
}
void add_line(int x1,int y1,int x2,int y2)
{
line[d].fun(x1,y1,y2,1); y[d++]=y1;
line[d].fun(x2,y1,y2,-1); y[d++]=y2;
}
int deal(int n)
{
sort(y,y+n);
sort(line,line+n,cmp);
int cnt=1;
for(int i=1;i<n;i++)
{
if(y[i]!=y[i-1]) y[cnt++]=y[i];
}
return cnt;
}