题目
http://acm.hdu.edu.cn/showproblem.php?pid=1542
题目大意
求所有矩形面积总和（矩形最多100个，坐标范围0~1e5）
算法思路
- 从下往上扫描，计算出高度为y时处于矩形中的长度总和，再乘以到上一条边的高度，就为该段矩形面积。
- 如何计算高度为y时处于矩形中的长度总和。扫描到矩形下边的时候，该段col值+1，表示此处被矩形覆盖，扫描到矩形上边时，该段col值-1，表示该段少了一个矩形覆盖。
- 我们把扫描到的长度相加往上pushup，所求的值就存在了顶点中，即sum[1]。
下面我们来看pushup函数:
void pushup(int rt,int l,int r){
if(col[rt]) sum[rt]=x[r+1]-x[l];
else if(l==r) sum[rt]=0;
else sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
col值大于0时表示其整一段被覆盖，计算该段长度。
col值等于0时，并不表示其没有被覆盖，可能其子段部分被覆盖。将子段数值相加往上推即可。
- 因为其坐标范围过大，数组存不下，所以要将其横坐标离散化。但若对点离散化之后，原来的区间[l,r]变为[l,mid],[mid+1,r]时，就会缺少一段，所以线段的区间采用左闭右开，因此上方函数中
sum[rt]=x[r+1]-x[l]。
另外从别人的博客上盗了一张图帮助理解
image
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=210;
struct seg{
double l,r,h;
int s;
bool operator< (const seg &b) const{
return h<b.h;
}s[maxn];
int col[maxn<<2];
double sum[maxn<<2];
double x[maxn<<2];
void pushup(int rt,int l,int r){
if(col[rt]) sum[rt]=x[r+1]-x[l];//[ )
else if(l==r) sum[rt]=0;
else sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int l,int r,int c,int rt,int ll,int rr){//l,r is fresh area
if(ll>=l&&rr<=r){
col[rt]+=c;
pushup(rt,ll,rr);
return;
}
int mid=(ll+rr)/2;
if(l<=mid) update(l,r,c,rt*2,ll,mid);
if(r>mid) update(l,r,c,rt*2+1,mid+1,rr);
pushup(rt,ll,rr);
}
int main(){
int n;int k=0;
while(cin>>n&&n){
k++;
int cnt=0;
for(int i=0;i<n;i++){
double a,b,c,d;
cin>>a>>b>>c>>d;
s[cnt]=seg{a,c,b,1};//bottom line
x[cnt++]=a;
s[cnt]=seg{a,c,d,-1};//top line
x[cnt++]=c;
}
sort(x,x+cnt);
sort(s,s+cnt,cmp);
int res=0;
for(int i=1;i<cnt;i++){
if(x[i]!=x[i-1])
x[++res]=x[i];
}
memset(col,0,sizeof(col));
memset(sum,0,sizeof(sum));
double ans=0;
for(int i=0;i<cnt-1;i++){
int l=lower_bound(x,x+res+1,s[i].l)-x;//find the index after discretization
int r=lower_bound(x,x+res+1,s[i].r)-x-1;//attention -1
update(l,r,s[i].s,1,0,res);
ans+=sum[1]*(s[i+1].h-s[i].h);
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n",k,ans);
}
}
