这道题是离散化的入门题。
问题描述:一些已知右下顶点和左上顶点坐标的矩形,这些矩形可能部分重叠,求它们所占的实际面积。
方案一、
把矩形映射到数组M[ ][ ]中,如果某矩形的位置为(x1,y1)(x2,y2)则M[i][j]=1(其中x1<=i<=x2,y1<=j<=y2)。但是,如果坐标值离散程度很大或者非整型,此方案就不可行。
方案二、
判断任两个矩形是否相交,如果重叠,两面积相加,减去重叠部分。但重叠情况很多,算法不复杂但程序写起来很复杂,容易出错。
方案三——离散化
1、首先分离出所有的横坐标和纵坐标分别按升序存入数组X[ ]和Y[ ]中.
2、 设数组XY[ ][ ].对于每个矩形(x1,y1)(x2,y2)确定i1,i2,j1,j2,使得,X[i1]>x1,X[i2]<=x2,Y[i1]>y1,Y[i2]>=y2令XY[ i ][ j ] = 1 (i从i1到i2,j从j1到j2)
3、统计面积:area+=XY[i][j] *(X[i]-X[i-1])*(Y[i] – Y[i-1])

#include<iostream>
using namespace std;
double x[201],y[201],s[101][4];
int xy[201][201];
int n,cas=0;
double sum;
int main()
{
    
int i,j,k;
    
while(cin>>n)
    {   
        
if(n==0)
            
break;
        cas
++;
        k
=0;
        sum
=0.0;
        memset(xy,
0,sizeof(xy));
        
for(i=1;i<=n;i++)
        {
            cin
>>s[i][0]>>s[i][1]>>s[i][2]>>s[i][3];
            x[k]
=s[i][0];
            y[k]
=s[i][1];
            k
++;
            x[k]
=s[i][2];
            y[k]
=s[i][3];
            k
++;
        }
        sort(x,x
+2*n);
        sort(y,y
+2*n);
        
for(k=1;k<=n;k++)
        {
            
int i1,i2,j1,j2;
            
for(i1=0;i1<2*n;i1++)
            {
                
if(x[i1]==s[k][0])
                    
break;
            }
            
for(i2=0;i2<2*n;i2++)
            {
                
if(x[i2]==s[k][2])
                    
break;
            }
            
for(j1=0;j1<2*n;j1++)
            {
                
if(y[j1]==s[k][1])
                    
break;
            }
            
for(j2=0;j2<2*n;j2++)
            {
                
if(y[j2]==s[k][3])
                    
break;
            }
            
for(i=i1;i<i2;i++)
            {
                
for(j=j1;j<j2;j++)
                {
                    xy[i][j]
=1;
                }
            }
        }
        
for(i=0;i<2*n;i++)
        {
            
for(j=0;j<2*n;j++)
            {
                sum
+=xy[i][j]*(x[i+1]-x[i])*(y[j+1]-y[j]);
            }
        }
        printf(
"Test case #%d\n",cas);
        printf(
"Total explored area: %.2f\n",sum);
        printf(
"\n");
    }
    system(
"pause");
    
return 0;
}