題目
http://acm.hdu.edu.cn/showproblem.php?pid=1542
題目大意
求所有矩形面積總和（矩形最多100個，坐標范圍0~1e5）
算法思路
- 從下往上掃描炊汤，計算出高度為y時處于矩形中的長度總和正驻，再乘以到上一條邊的高度，就為該段矩形面積抢腐。
- 如何計算高度為y時處于矩形中的長度總和姑曙。掃描到矩形下邊的時候，該段col值+1迈倍，表示此處被矩形覆蓋伤靠，掃描到矩形上邊時，該段col值-1啼染，表示該段少了一個矩形覆蓋宴合。
- 我們把掃描到的長度相加往上pushup，所求的值就存在了頂點中迹鹅，即sum[1]卦洽。
下面我們來看pushup函數(shù):
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時阀蒂，并不表示其沒有被覆蓋，可能其子段部分被覆蓋弟蚀。將子段數(shù)值相加往上推即可蚤霞。
- 因為其坐標范圍過大，數(shù)組存不下义钉，所以要將其橫坐標離散化昧绣。但若對點離散化之后，原來的區(qū)間[l,r]變?yōu)閇l,mid],[mid+1,r]時捶闸，就會缺少一段夜畴，所以線段的區(qū)間采用左閉右開，因此上方函數(shù)中
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);
}
}
