Title Link: http://acm.hdu.edu.cn/showproblem.php?pid=1255
Title:
Give N (N < = 1000) rectangles and find the sum of the area covered by at least two rectangles.
Train of thought:
And the last blog link The idea of finding the intersection of multiple rectangles is very similar. That is to maintain the current effective width to find the area union. Here, we only need to treat the cnt [i] > = 2 as the effective width (because cnt records the coverage of scan line, when a certain interval is covered by the bottom edge at least twice, then the area above the edge is formed by the intersection of at least two rectangles). So the only difference is to update le When n (effective len gth of interval), the cnt is considered.
Code:
#include<bits/stdc++.h>
#define lson l,mid,o<<1
#define rson mid+1,r,o<<1|1
#define N 2005
using namespace std;
int cnt[N<<2];
double len[N<<2];
double X[N<<1];
struct edge
{
double l,r,h;
int f;
edge() {}
edge(double l,double r,double h,int f):l(l),r(r),h(h),f(f) {}
bool operator < (const edge &b) const
{
return h<b.h;
}
} e[N<<1];
void push_up(int o)
{
if(cnt[o<<1]==-1 || cnt[o<<1|1]==-1)
cnt[o]=-1;
else if(cnt[o<<1]!=cnt[o<<1|1])
cnt[o]=-1;
else
cnt[o]=cnt[o<<1];
len[o]=len[o<<1]+len[o<<1|1];
}
void push_down(int o,int l,int r)
{
if(cnt[o]!=-1)
{
int mid=l+r>>1;
cnt[o<<1]=cnt[o<<1|1]=cnt[o];
len[o<<1]=(cnt[o]>=2 ? X[mid+1]-X[l] :0);
len[o<<1|1]=(cnt[o]>=2 ? X[r+1]-X[mid+1] :0);
}
}
void build(int l,int r,int o)
{
if(l==r)
{
cnt[o]=0;
len[o]=0.0;
return;
}
int mid=l+r>>1;
build(lson);
build(rson);
push_up(o);
}
void update(int L,int R,int v,int l,int r,int o)
{
if(L<=l&&r<=R)
{
if(cnt[o]!=-1)
{
cnt[o]+=v;
len[o]=(cnt[o]>=2 ? X[r+1]-X[l]:0);
return;
}
}
push_down(o,l,r);
int mid=l+r>>1;
if(L<=mid)
update(L,R,v,lson);
if(R>mid)
update(L,R,v,rson);
push_up(o);
}
int main()
{
int n,t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
double x1,y1,x2,y2;
for(int i=1; i<=n; i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
X[i]=x1,X[i+n]=x2;
e[i]=edge(x1,x2,y1,1);
e[i+n]=edge(x1,x2,y2,-1);
}
sort(e+1,e+1+2*n);
int m=unique(X+1,X+1+2*n)-X-1;
sort(X+1,X+1+m);
build(1,m-1,1); //m different points are divided into m-1 intervals
double ans=0.0;
for(int i=1; i<=2*n-1; i++)
{
int l=lower_bound(X+1,X+1+m,e[i].l)-X;
int r=lower_bound(X+1,X+1+m,e[i].r)-X-1;
//printf("%d %d\n",l,r);
update(l,r,e[i].f,1,m-1,1);
//printf("%f %f\n",len[1],e[i+1].h-e[i].h);
ans+=len[1]*(e[i+1].h-e[i].h);
}
printf("%.2lf\n",ans);
}
return 0;
}