亚特兰蒂斯(扫描线+离散化+线段树)
题意:
求n个可能有交集的矩形的面积和
题解:
从左往右枚举坐标x,用线段树维护坐标y,扫描线分块求每个小块的面积和
1)线段树叶子节点的是一段区间
2)我们每次取的是根节点的区间长度,所以不需要query
操作
3)为何不需要懒标记?
query
操作只查询根节点,不会用到pushdown
- 由于扫描线的特殊性,每次区间查询都会自行抵消,所以
modify
操作可以不用进行pushdown
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
//存储线段的信息
struct P1{
double x,y1,y2;
int k;
bool operator<(const P1 &t)const{
return x<t.x;
}
}g[N*2];
// 线段树的每个节点 保存的为线段,0号点为y[0]到y[1],以此类推
struct P2{
int l,r;
double len;//区间长度
int cnt;//判断是否算作长度
}tr[8*N];
//离散化后的y坐标位置
vector<double>ve;
int n;
int find(double x){
return lower_bound(ve.begin(),ve.end(),x)-ve.begin();
}
void pushup(int u){
if(tr[u].cnt) tr[u].len=ve[tr[u].r+1]-ve[tr[u].l];//如果cnt>0,注意不能+1(区间长度)
else if(tr[u].l!=tr[u].r){//如果不是叶子节点
tr[u].len=tr[u<<1].len+tr[u<<1|1].len;
}
else tr[u].len=0;
}
void build(int u,int l,int r){
if(l==r) tr[u]={l,r,0,0};
else{
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
}
void modify(int u,int l,int r,int v){
if(tr[u].l>=l&&tr[u].r<=r){
tr[u].cnt+=v;
pushup(u);//u节点cnt的改变可能会导致len的改变,所以需要在这个地方pushup,在之前的题目中,u的值只与他的子孙节点有关,而本题中len可能由自身cnt的取值更新。
}
else{
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify(u<<1,l,r,v);
if(r>mid) modify(u<<1|1,l,r,v);
pushup(u);
}
}
int main(){
int T=1;
while(cin>>n,n){
ve.clear();
for(int i=0,j=0;i<n;i++){
double x1,x2,y1,y2; cin>>x1>>y1>>x2>>y2;
g[j++]={x1,y1,y2,1};
g[j++]={x2,y1,y2,-1};
ve.push_back(y1),ve.push_back(y2);//离散化存放y轴坐标
}
//离散化
sort(ve.begin(),ve.end());
ve.erase(unique(ve.begin(),ve.end()),ve.end());
build(1,0,ve.size()-2);//每个叶子节点tr[i]代表一个区间[ve[i],vr[i+1]]
//对x轴排序
sort(g,g+2*n);
double ans=0;
for(int i=0;i<2*n;i++){
if(i) ans+=(g[i].x-g[i-1].x)*tr[1].len;//判断i点之前的那个区间的面积
modify(1,find(g[i].y1),find(g[i].y2)-1,g[i].k);//注意find(g[i].y2)-1,因为线段树的叶子节点代表的是一个区间
}
printf("Test case #%d\n",T++);
printf("Total explored area: %.2lf\n\n",ans);
}
return 0;
}