poj 1151(离散化+矩形面积并)

Arce

题目链接：http://poj.org/problem?id=1151
关于离散化,这篇博客讲的很好：http://www.cppblog.com/MiYu/archive/2010/10/15/129999.aspx
我线段树还是不会写这个。。
借个图：

///离散化
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cmath>
using namespace std;
const int N = 220;
const double eps = 1e-10;
struct Rec{
  double x1,y1;
  double x2,y2;
}rec[N];
double x[N],y[N];
int vis[N][N];
int n,k;
int cmp(double a,double b){
  if(a<b) return 1;
  return 0;
}
void input(){
  k = 0;
  for(int i=0;i<n;i++){
    scanf("%lf%lf%lf%lf",&rec[i].x1,&rec[i].y1,&rec[i].x2,&rec[i].y2);
    x[k] = rec[i].x1,y[k++] = rec[i].y1;
    x[k] = rec[i].x2,y[k++] = rec[i].y2;
  }
  sort(x,x+k,cmp);
  sort(y,y+k,cmp);
}
int binary1(double value){
  int mid,l=0,r=k-1;
  while(l<r){
    mid = (l+r)>>1;
    if(fabs(x[mid]-value)<eps) return mid;
    if(x[mid]<value) l = mid+1;
    else r = mid-1;
  }
  return l;
}
int binary2(double value){
  int mid,l=0,r=k-1;
  while(l<r){
    mid = (l+r)>>1;
    if(fabs(y[mid]-value)<eps) return mid;
    if(y[mid]<value) l = mid+1;
    else r = mid-1;
  }
  return l;
}
double solve(){
  int t1,t2,t3,t4;
  for(int i=0;i<n;i++){
    t1 = binary1(rec[i].x1);
    t2 = binary1(rec[i].x2);
    t3 = binary2(rec[i].y1);
    t4 = binary2(rec[i].y2);
    for(int j=t1;j<t2;j++){
      for(int l = t3;l<t4;l++){
        vis[j][l]=1;
      }
    }
  }
  double area = 0;
  for(int i=0;i<k;i++){
    for(int j=0;j<k;j++){
      area+=vis[i][j]*(x[i+1]-x[i])*(y[j+1]-y[j]);
    }
  }
  return area;
}
int main()
{
  int cnt=1;
  while(scanf("%d",&n)!=EOF&&n){
    memset(vis,0,sizeof(vis));
    input();
    printf("Test case #%d\nTotal explored area: %.2lf\n\n",cnt++,solve());
  }
  return 0;
}