Atlantis HDU - 1542（线段树扫描线）

题目

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);
    }
}