セグメントツリー再開HDU 1542(走査線)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <cctype>
#include <deque>
using namespace std;
typedef long long LL;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int N = 300;
struct node{
  int flag;
  double p,h1,h2;
  node(int x=0,double y=0,double z=0,double w=0):
      flag(x),p(y),h1(z),h2(w){}

  bool operator <(const node& rhs)const{
    if(p!=rhs.p) return p<rhs.p;
    return flag<rhs.flag;
  }
};
node st[N<<1];
double sum[N<<2],x[N<<1];
int col[N<<2];
void build(int l,int r,int rt){
  sum[rt] = col[rt] = 0;
  if(l==r) return ;
  int m = (l+r)>>1;
  build(lson);
  build(rson);
}
void upd_one_seg(int l,int r,int rt){
   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 rt,int L,int R,int v){
  if(L<=l&&r<=R){
     col[rt]+=v;
     upd_one_seg(l,r,rt);
     return ;
  }
  int m = (l+r)>>1;
  if(L<=m) update(lson,L,R,v);
  if(R> m) update(rson,L,R,v);
  upd_one_seg(l,r,rt);
}
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int (i)=1;(i)<=(n);(i)++)

int n;
int find(double* A,int t,double v){
  int x=1,y=t;
  while(x<y){
    int mid = (x+y)>>1;
    if(A[mid] == v) return mid;
    else if(A[mid] < v) x=mid+1;
    else y = mid;
  }
}
int main()
{
    int kase=1;
   while(scanf("%d",&n)==1&&n){
     int m = 1;
     for(int i=0;i<n;i++){
       double a,b,c,d;
       scanf("%lf %lf %lf %lf",&a,&b,&c,&d);
       x[m] = b;
       st[m++] = node(1,a,b,d);
       x[m] = d;
       st[m++] = node(-1,c,b,d);
     }
     sort(x+1,x+m);
     sort(st+1,st+m);
     int cnt = unique(x+1,x+m) - x;
     build(1,cnt,1);
     double res = 0;
     for(int i=1;i<m;i++){
        if(i>1&&st[i].p!=st[i-1].p){
            res+=sum[1]*(st[i].p-st[i-1].p);
        }
        int L = find(x,cnt,st[i].h1) ,R = find(x,cnt,st[i].h2)-1;
        update(1,cnt,1,L,R,st[i].flag);
     }
     printf("Test case #%d
Total explored area: %.2lf

",kase++,res);
   }
   return 0;
}