poj 1151 離散化

題目大意：給出 n 個矩形的“左下”和“右上”頂點坐標，求面積並；

思路：由於坐標值為實數，所以不能直接用數組模擬，要先將所有坐標值離散化處理；

[cpp]  #include<iostream>  
#include<stdio.h>  
#include<string.h>  
#include<stdlib.h>  
#include<algorithm>  
using namespace std; 
#define SIZE 103<<1  
double a[SIZE][4],x[SIZE],y[SIZE]; 
int map[SIZE][SIZE]; 
int main() 
{ 
    int T=1,n,i,j,l,k; 
    int x1,y1,x2,y2; 
    while(scanf("%d",&n),n){ 
        for(i=0,k=0;i<n;i++){ 
            scanf("%lf%lf%lf%lf",&a[i][0],&a[i][1],&a[i][2],&a[i][3]); 
            x[k]=a[i][0]; 
            y[k]=a[i][1]; 
            k++; 
            x[k]=a[i][2]; 
            y[k]=a[i][3]; 
            k++; 
        } 
        sort(x,x+k); 
        sort(y,y+k); 
        memset(map,0,sizeof(map)); 
        for(i=0;i<n;i++){ 
            for(x1=0;x1<k;x1++){ 
                if(x[x1]==a[i][0]) 
                    break; 
            } 
            for(y1=0;y1<k;y1++){ 
                if(y[y1]==a[i][1]) 
                    break; 
            } 
            for(x2=0;x2<k;x2++){ 
                if(x[x2]==a[i][2]) 
                    break; 
            } 
            for(y2=0;y2<k;y2++){ 
                if(y[y2]==a[i][3]) 
                    break; 
            } 
            for(l=x1;l<x2;l++){ 
                for(j=y1;j<y2;j++){ 
                    map[l][j]=1; 
                } 
            } 
        } 
        double sum=0; 
        for(i=0;i<k-1;i++){ 
            for(j=0;j<k-1;j++){ 
                if(map[i][j]==1){ 
                    sum+=(x[i+1]-x[i])*(y[j+1]-y[j]); 
                } 
            } 
        } 
        printf("Test case #%d\n",T++); 
        printf("Total explored area: %.2lf\n\n",sum); 
    } 
    return 0; 
} 

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define SIZE 103<<1
double a[SIZE][4],x[SIZE],y[SIZE];
int map[SIZE][SIZE];
int main()
{
 int T=1,n,i,j,l,k;
 int x1,y1,x2,y2;
 while(scanf("%d",&n),n){
  for(i=0,k=0;i<n;i++){
   scanf("%lf%lf%lf%lf",&a[i][0],&a[i][1],&a[i][2],&a[i][3]);
   x[k]=a[i][0];
   y[k]=a[i][1];
   k++;
   x[k]=a[i][2];
   y[k]=a[i][3];
   k++;
  }
  sort(x,x+k);
  sort(y,y+k);
  memset(map,0,sizeof(map));
  for(i=0;i<n;i++){
   for(x1=0;x1<k;x1++){
    if(x[x1]==a[i][0])
     break;
   }
   for(y1=0;y1<k;y1++){
    if(y[y1]==a[i][1])
     break;
   }
   for(x2=0;x2<k;x2++){
    if(x[x2]==a[i][2])
     break;
   }
   for(y2=0;y2<k;y2++){
    if(y[y2]==a[i][3])
     break;
   }
   for(l=x1;l<x2;l++){
    for(j=y1;j<y2;j++){
     map[l][j]=1;
    }
   }
  }
  double sum=0;
  for(i=0;i<k-1;i++){
   for(j=0;j<k-1;j++){
    if(map[i][j]==1){
     sum+=(x[i+1]-x[i])*(y[j+1]-y[j]);
    }
   }
  }
  printf("Test case #%d\n",T++);
  printf("Total explored area: %.2lf\n\n",sum);
 }
 return 0;
}