矩形的并的面积

描述

在 X-Y 坐标平面上，给定多个矩形，它们的边分别与坐标轴平行。请计算它们的并的面积。

输入格式

输入第一行为一个整数 n，1<=n<=100，表示矩形的数量。

接下来有 n 行，每行包括四个数：x1,y1,x2,y2 (0<=x1<x2<=100000;0<=y1<y2<=100000)，用空格分开，不一定为整数。

(x1,y1)表示一个长方形的左下顶点坐标，(x2,y2)表示右上顶点坐标。

输出格式

n个矩形的并的面积，保留两位小数。

输入样例

0 0 2 2

1 1 3 3

输出样例

7.00

分析

（离散化）

多个矩形重叠，重叠情况有很多种，不能进行直接计算，可以将二维坐标划分为一个个小的矩形，保证小矩形不存在重叠，然后对全部小矩形进行分析，将包含在原来题目给出的n个矩形中的小矩形标志，最后将标志的矩形面积相加就是结果；

怎么样进行二维坐标的划分呢？以所有的矩形边（4条）作为划分界线，可以保证到每个划分的小矩形都不重叠。如图：

可以看出小矩形是不存在重复的。

下一步：将矩形的X坐标（每个矩形有两个）和Y坐标（两个）保存在X[] 数组和Y[] 数组，并排序。

从图中可以看出，小矩形左下坐标位于大矩形类时 (X[i],Y[i])与 (X[i+1],Y[i+1])就是包含在大矩形类。

代码实现

#include<stdio.h>  
#include<stdlib.h>  
   
struct rectangle{    //结构体，保存矩形  
       float x1;  
       float y1;  
       float x2;  
       float y2;  
       };  
         
rectangle arr[101];      
float x[200];  
float y[200];  
 int flag[200][200];  
  
  
int Partition(float a[],int low,int high){  
    float pivotkey=a[low];  
      
    while(low<high){  
                    while(low<high&&a[high]>=pivotkey)  
                        --high;  
                    a[low]=a[high];  
                    while(low<high&&a[low]<=pivotkey)  
                        ++low;  
                    a[high]=a[low];  
                    }  
    a[low]=pivotkey;  
    return low;  
}  
  
void QSort(float a[],int low,int high){     //快速排序  
     if(low<high){  
                  int pivotloc=Partition(a,low,high);  
                  QSort(a,low,pivotloc-1);  
                  QSort(a,pivotloc+1,high);  
                  }  
     }  
         
int main(){  
     
   float count=0;  
   int n;  
   int k=0;  
   scanf("%d",&n);                             //数据输入  
    for(int i=0;i<n;i++){           
            scanf("%f",&arr[i].x1);  
            scanf("%f",&arr[i].y1);  
            scanf("%f",&arr[i].x2);  
            scanf("%f",&arr[i].y2);  
            x[k]=arr[i].x1;                   //保存所有X坐标到X[]数组,Y 到Y[]数组  
            y[k]=arr[i].y1;  
            k++;  
            x[k]=arr[i].x2;  
            y[k]=arr[i].y2;  
            k++;  
            }  
    QSort(x,0,2*n-1);         //分别排序       
    QSort(y,0,2*n-1);  
      
      
              
   for(int h=0;h<n;h++)          //循环查找在矩形内的小矩形  
       for(int i=0;i<2*n;i++){  
          if(x[i]>=arr[h].x2)  
              break;       
          for(int j=0;j<2*n;j++){  
             if(y[j]>=arr[h].y2)  
                break;  
             if(x[i]>=arr[h].x1&&y[j]>=arr[h].y1)  
                flag[i][j]=1;                       //符合，标志  
          }  
       }  
                                     
      
                
    for(int i=0;i<2*n;i++)               //统计面积  
       for(int j=0;j<2*n;j++)  
          count+=flag[i][j]*(x[i+1]-x[i])*(y[j+1]-y[j]);       
               
            
    printf("%.2f",count);  
        
   return 0;  
   
}

补充：软件开发 , C++ ,