HDU 1542：Atlantis（线段树+扫描线+离散化）

线段树+扫描线+离散化模板题目

第一次做这种类型的题目，以前以为比较难，就没敢碰它，现在学起来感觉还挺简单的，对于我来说，这种离散化思想要稍微难理解一点，其他的部分挺简单的

又学到了新东西！！！

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=220;

struct Node{
  
  double l,r;
  double h;
  int type;
  Node(double l_=0,double r_=0,double h_=0,int type_=0):l(l_),r(r_),h(h_),type(type_){}
}node[maxn];
double x[maxn];
int tot;

double tree[maxn<<2];
int cnt[maxn<<2];

inline bool cmp(Node a,Node b){
  
  return a.h<b.h;
}

inline int getX_Ind(double locate){
  
  int l=1;
  int r=tot;
  while(l<=r){
    
    int mid=(l+r)>>1;
    if(x[mid]==locate) return mid;
    if(x[mid]<locate) l=mid+1;
    else r=mid-1; 
  }
}

inline void PushUp(int root,int l,int r){
  
  if(cnt[root]) tree[root]=x[r+1]-x[l];
  else if(l==r) tree[root]=0;
  else tree[root]=tree[root<<1]+tree[root<<1|1];
}

inline void Update(int root,int l,int r,int L,int R,int v){
  
  if(L<=l && R>=r){
    
    cnt[root]+=v;
    PushUp(root,l,r);
    return ;
  }
  int mid=(l+r)>>1;
  if(R<=mid) Update(root<<1,l,mid,L,R,v);
  else if(L>mid) Update(root<<1|1,mid+1,r,L,R,v);
  else Update(root<<1,l,mid,L,R,v),Update(root<<1|1,mid+1,r,L,R,v);
  PushUp(root,l,r);
}

int main(){
  
  int n,m;
  int C=0;
  while(scanf("%d",&n)==1&&n){
    
    m=2*n;
    for(int i=0;i<n;i++){
      
      double x1,y1,x2,y2;
      scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
      int l=i*2+1;
      int r=i*2+2;
      node[l]=Node(x1,x2,y1,1);
      x[l]=x1;
      node[r]=Node(x1,x2,y2,-1);
      x[r]=x2;
    }
    sort(x+1,x+m+1);
    sort(node+1,node+m+1,cmp);
    
    tot=1;
    double area=0;
    for(int i=2;i<=m;i++) if(x[i]!=x[i-1]) x[++tot]=x[i];
    for(int i=1;i<=m;i++){
      
      int L=getX_Ind(node[i].l);
      int R=getX_Ind(node[i].r)-1;
      Update(1,1,tot,L,R,node[i].type);
      if(i!=m) area+=tree[1]*(node[i+1].h-node[i].h);
    }
    printf("Test case #%d\nTotal explored area: %.2f\n\n",++C,area);
  }
}