POJ 1151 Atlantis解题报告

时间：2010-05-28 来源：MC_ACM

题目大意：

给出平面上的一系列有可能重叠的矩形（矩形的位置用矩形左上角的坐标和右下角的坐标进行标示），求出总的覆盖面积。矩形的数量1<=n<=100，坐标的位置0<x,y<100000。

解题思路：

采取离散化的方法。

1、首先分离出所有的横坐标和纵坐标分别存入数组x[]和y[]中，并按非降序进行排序；

2、所有矩形的每一条边将整个平面最多分割成201×201块区域，其中199×199块是有限区域，使用flag[][]数组记录每一块区域是否在矩形的内部，初始化为false。标注每一块是否在矩形内部的时候，对于每个矩形(x1,y1)(x2,y2)，令flag[i][j] = true (i从x1到x2，j从y1到y2)；

3、对矩形的边分割平面的每一块进行面积统计：ans+=flag[i][j]*(x[i+1]-x[i])*(y[j+1]-y[j])。

输入输出格式：

Sample Input

10 10 20 20

15 15 25 25.5

Sample Output

Test case #1

Total explored area: 180.00

题目代码：

#include <iostream>
#include <cmath>

using namespace std;
const int N=100;
const double epx = 1e-9;
double ans,pos[N][4];
double x[2*N],y[2*N];
bool flag[2*N][2*N];

int cmp(const void *a,const void *b){
     double *aa = (double *)a;
     double *bb = (double *)b;
     if(fabs(*aa-*bb)<=epx) return 0;
     else if(*aa-*bb>0) return 1;
     else return -1;
}

int main()
{
    int num,x1,x2,y1,y2,i,j,k,ca=1;
    scanf("%d",&num);
    while(num>0)
    {
        for(ans=k=i=0;i<num;i++,k+=2)
        {
            scanf("%lf %lf %lf %lf",&pos[i][0],&pos[i][1],&pos[i][2],&pos[i][3]);
            x[k]=pos[i][0];
            y[k]=pos[i][1];
            x[k+1]=pos[i][2];
            y[k+1]=pos[i][3];
        }
        memset(flag,false,sizeof(flag));
        qsort(x,2*num,sizeof(x[0]),cmp);
        qsort(y,2*num,sizeof(y[0]),cmp);
        for(i=0;i<num;i++)
        {
            for(j=0;fabs(x[j]-pos[i][0])>epx;j++);
                x1=j;
            for(j=0;fabs(y[j]-pos[i][1])>epx;j++);
                y1=j;
            for(j=0;fabs(x[j]-pos[i][2])>epx;j++);
                x2=j;
            for(j=0;fabs(y[j]-pos[i][3])>epx;j++);
                y2=j;
            for(j=x1;j<x2;j++)
                for(k=y1;k<y2;k++)
                    flag[j][k]=true;
        }
        for(i=0;i<2*num-1;i++)
            for(j=0;j<2*num-1;j++)
                ans+=flag[i][j]*(x[i+1]-x[i])*(y[j+1]-y[j]);

        printf("Test case #%d\n",ca++);
        printf("Total explored area: %.2lf\n",ans);
        printf("\n");
        scanf("%d",&num);
    }
    return 0;
}