這道題是離散化的入門(mén)題。
問(wèn)題描述：一些已知右下頂點(diǎn)和左上頂點(diǎn)坐標(biāo)的矩形，這些矩形可能部分重疊，求它們所占的實(shí)際面積。
方案一、
把矩形映射到數(shù)組M[ ][ ]中，如果某矩形的位置為（x1，y1）（x2，y2）則M[i][j]=1（其中x1<=i<=x2,y1<=j<=y2）。但是，如果坐標(biāo)值離散程度很大或者非整型，此方案就不可行。
方案二、
判斷任兩個(gè)矩形是否相交，如果重疊，兩面積相加，減去重疊部分。但重疊情況很多，算法不復(fù)雜但程序?qū)懫饋?lái)很復(fù)雜，容易出錯(cuò)。
方案三——離散化
1、首先分離出所有的橫坐標(biāo)和縱坐標(biāo)分別按升序存入數(shù)組X[ ]和Y[ ]中.
2、 設(shè)數(shù)組XY[ ][ ].對(duì)于每個(gè)矩形(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到j(luò)2)
3、統(tǒng)計(jì)面積：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;
}