偶看新闻旅游景区商业计划书:（求矩形并的面积）-区域离散化
来源：百度文库 编辑：偶看新闻 时间：2024/04/19 21:20:19
在二维坐标中给出若干矩形，矩形间可以产生重叠，现在求这些矩形所覆盖的二维平面上的区域的面积。
算法：单个矩形面积好求，但，多个矩形进行重叠，这样形成的区域没有规律性，面积不好求。既然整体面积难求，就局部的进行求解（离散思想）。
对于输入的所有矩形，我们存储每个矩形的信息（对角的点坐标，存于rec数组中，两对角点为（rec0，rec1），（rec2，rec3）），然后定义两个一维数组x和y，用来存储所有矩形的所有的横坐标和纵坐标（每个矩形有两个横坐标和两纵坐标），之后对x和y中的元素分别进行升序排序，这样x和y中的坐标的依次组合能将平面分为多个区域。再定义一个二维数组flag。对于一个矩形（（rec0，rec1），（rec2，rec3）），我们要找到一个x[i]和一个y[j]，使它们满足x[i]>=rec0&&x[i]
那么这块区域的面积s=flag[i][j]*(x[i+1]-x[i])*(y[j+1]-y[j]);
当我们沿着x和y数组顺序进行查找，并置相应的flag为1，而其它的flag为0（表示这样的区域没有被矩形覆盖，那么上式的s值为0），这样，将平面内所有离散后的区域的s加起来，就是我们要求的矩形并的面积了。.
程序代码：
#include"iostream"
#include"cstdio"
#include"algorithm"
#define M 202
using namespace std;
void fun(int n,int cases)
{
int flag[M][M];/*标记该块是否在矩形内，是为1，否则为0*/
double x[M],y[M];
double rec[M][4];
int i,j=0,k;
double sum=0;
memset(flag,0,sizeof(flag));
for(i=0;i
scanf("%lf%lf%lf%lf",&rec[i][0],&rec[i][1],&rec[i][2],&rec[i][3]);
x[j]=rec[i][0];
y[j]=rec[i][1];
++j;
x[j]=rec[i][2];
y[j]=rec[i][3];
++j;
}
sort(x,x+2*n);
sort(y,y+2*n);
for(i=0;i
for(j=0;j<2*n;j++)
{
if(x[j]>=rec[i][2])
break;
for(k=0;k<2*n;k++)
{
if(y[k]>=rec[i][3])
break;
if(x[j]>=rec[i][0]&&y[k]>=rec[i][1])
flag[j][k]=1;
}
}
}
for(i=0;i<2*n;i++)
for(j=0;j<2*n;j++)
sum+=flag[i][j]*(x[i+1]-x[i])*(y[j+1]-y[j]);
printf("Test case #%d\nTotal explored area: %.2lf\n\n",cases,sum);
}
int main()
{
int n;
int cases=0;
while(scanf("%d",&n)&&n)
{
++cases;
fun(n,cases);
}
//system("pause");
return 0;
}