文章详情

  • 游戏榜单
  • 软件榜单
关闭导航
热搜榜
热门下载
热门标签
php爱好者> php文档>pku1151 Atlantis

pku1151 Atlantis

时间:2010-08-09  来源:Z_Q_2010

#include<stdio.h>
#include<algorithm>
using namespace std;

const int Maxn=110;
double vertical[Maxn*2],horizon[Maxn*2];
bool visit[Maxn*2][Maxn*2];            //标识由超元线段所围成的单元矩形被访问


struct rectangle
{
    double x1,x2,y1,y2;
};
rectangle rec[Maxn];
int n;

int cmp(const void *a,const void *b)
{
    return *(double *)a>*(double *)b?1:-1;        //若直接a,b做差,由double返回int可能出现偏差

}

int main()
{
    int count=0;
    while(scanf("%d",&n),n)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf%lf%lf",&rec[i].x1,&rec[i].y1,&rec[i].x2,&rec[i].y2);
            horizon[2*i]=rec[i].x1;horizon[2*i+1]=rec[i].x2;
            vertical[2*i]=rec[i].y1;vertical[2*i+1]=rec[i].y2;
        }

        qsort(vertical,2*n,sizeof(double),cmp);
        qsort(horizon,2*n,sizeof(double),cmp);

        for(int i=0;i<2*n;i++)
            for(int j=0;j<2*n;j++)
                visit[i][j]=false;

        double sum=0;
        for(int i=1;i<2*n;i++)
        {
            if(horizon[i]==horizon[i-1])    continue;

            for(int j=0;j<n;j++)
            {
                if(rec[j].x1<=horizon[i-1]&&rec[j].x2>=horizon[i])
                {
                    for(int k=1;k<2*n;k++)
                    {
                        if(vertical[k]==vertical[k-1])    continue;

                        if(rec[j].y1<=vertical[k-1]&&rec[j].y2>=vertical[k]&&!visit[i][k])
                        {
                            sum+=(horizon[i]-horizon[i-1])*(vertical[k]-vertical[k-1]);
                            visit[i][k]=true;
                        }
                    }
                }
            }
        }
        printf("Test case #%d\nTotal explored area: %.2lf\n\n",++count,sum);
    }
    return 0;
}

 

关于离散化的具体内容,可以参看国家集训队1999年论文集

相关阅读 更多 +
排行榜 更多 +
辰域智控app

辰域智控app

系统工具 下载
网医联盟app

网医联盟app

运动健身 下载
汇丰汇选App

汇丰汇选App

金融理财 下载