题目大意:给定 N 个矩形,求这些矩形的面积并。
题解:采用扫描线算法。
首先,按照矩形的横坐标排序,在纵坐标方向上维护一根扫描线被覆盖的长度,在这里采用线段树维护。统计答案时,从左到右扫描 2N 个 X 坐标,两个坐标之间的扫描线被覆盖的长度相等,因此直接长乘宽计入答案即可。
注意事项
- 由于坐标不是整数,因此采用离散化。
- 线段树动态开点即可。
- 跟以往线段树不同的地方在于,这里的线段树的区间修改并没有没有下传标记。原因可以总结为查询时只询问根节点的信息,没有必要下传标记。
代码如下
#include <cstdio>
#include <iostream>
#include <memory>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=210;
int n,kase;
struct re{
double x,y,y1;
int is;
}rec[maxn];
bool cmp(const re &a,const re &b){return a.x<b.x;}
double d[maxn];int cnt;
inline int query(double x){return lower_bound(d+1,d+cnt+1,x)-d;}
struct node{
#define ls(x) t[x].lc
#define rs(x) t[x].rc
int lc,rc,tag;
double len;
}t[maxn<<1];
int tot,root;
inline void maintain(int o,int l,int r){
if(t[o].tag>0)t[o].len=d[r+1]-d[l];
else t[o].len=t[ls(o)].len+t[rs(o)].len;
}
void modify(int &o,int l,int r,int x,int y,int val){
if(!o)o=++tot;
if(l==x&&r==y){t[o].tag+=val;maintain(o,l,r);return;}
int mid=l+r>>1;
if(y<=mid)modify(ls(o),l,mid,x,y,val);
else if(x>mid)modify(rs(o),mid+1,r,x,y,val);
else modify(ls(o),l,mid,x,mid,val),modify(rs(o),mid+1,r,mid+1,y,val);
maintain(o,l,r);
}
void read_and_parse(){
for(int i=1;i<=n;i++){
scanf("%lf%lf%lf%lf",&rec[i].x,&rec[i].y,&rec[i+n].x,&rec[i+n].y);
rec[i].y1=rec[i+n].y,rec[i+n].y1=rec[i].y;
rec[i].is=0,rec[i+n].is=1;
d[i]=rec[i].y,d[i+n]=rec[i+n].y;
}
sort(rec+1,rec+2*n+1,cmp);
sort(d+1,d+2*n+1);
cnt=unique(d+1,d+2*n+1)-d-1;
}
void solve(){
double ans=0;
for(int i=1;i<2*n;i++){
int l=query(rec[i].y),r=query(rec[i].y1);
if(!rec[i].is)modify(root,1,cnt-1,l,r-1,1);
else modify(root,1,cnt-1,r,l-1,-1);
ans+=(rec[i+1].x-rec[i].x)*t[root].len;
}
printf("Test case #%d\n",++kase);
printf("Total explored area: %.2lf\n",ans);
puts("");
}
int main(){
while(scanf("%d",&n)&&n){
memset(t,0,sizeof(t)),memset(rec,0,sizeof(rec));
tot=root=0;
read_and_parse();
solve();
}
return 0;
}