PKU 1379 Run Away(模拟退火算法)

给出指定的区域,以及平面内的点集,求出一个该区域内一个点的坐标到点集中所有点的最小距离最大.

解题思路：一开始想到用随机化算法解决，但是不知道如何实现。最后看了题解才知道原来是要用模拟退火算法解决。

不过个人感觉这个算法的实现过程中仍然采用了随机化算法。二者均属于概率算法。参考链接

Point Goto_Rand_Dir(double key,Point temp)函数中,Point temp必须得定义在参数中,不能定义在函数内部,

否则temp没有初始值,无法进行后面的加法运算.

#include<ctime>

#include<cmath>

#include<cstdio>

#include<cstdlib>

const int shift=;

const double inf=1e10;

const double pi=acos(-1.0);

struct Point

{

    double x,y;

}p[],randp[];

double Get_Dis(Point a,Point b)

{

    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);

}

Point Get_Rand_Point(int a,int b)

{

    Point temp;

    temp.x=rand()%a+;

    temp.y=rand()%b+;

    return temp;

}

Point Goto_Rand_Dir(double key,Point temp)

{

    double delta=*pi*(double)rand()/RAND_MAX;

    temp.x+=key*sin(delta);

    temp.y+=key*cos(delta);

    return temp;

}

int main()

{

    double dis[];

    int i,j,k,T,x,y,m;

    scanf("%d",&T);

    srand(time(NULL));

    while(T--){

        double now;

        Point temp;

        scanf("%d%d%d",&x,&y,&m);

        for(i=;i<=m;i++)

            scanf("%lf%lf",&p[i].x,&p[i].y);

        for(i=;i<=;i++){//分别往四个方向找四个方向的最小值

            dis[i]=inf;

            randp[i]=Get_Rand_Point(x,y);//给randp[]数组随机取横纵坐标值

            for(j=;j<=m;j++){

                now=Get_Dis(randp[i],p[j]);

                if(now<dis[i]) dis[i]=now;//dis[i]存的是最小值

            }

        }

        double key=sqrt(1.0*(x*x+y*y))/;//关键

        while(key>=0.01){//精度要求

            for(i=;i<=;i++){

                for(j=;j<=shift;j++){

                    temp=randp[i];//采用之前四个方向确定的随机横纵坐标值

                    temp=Goto_Rand_Dir(key,temp);

                    if(temp.x<||temp.y<||temp.x>x||temp.y>y)

                        continue;

                    now=inf;

                    for(k=;k<=m;k++){

                        double dist=Get_Dis(temp,p[k]);

                        if(now>dist) now=dist;//now存的是最小值

                    }

                    if(now>dis[i]){

                        dis[i]=now;//dis[i]中存的是最小值最大

                        randp[i]=temp;

                    }

                }

            }

            key=key*0.8;

        }

        for(i=,k=;i<=;i++)//在四个方向中找最小值最大

            if(dis[i]>dis[k]) k=i;

        printf("The safest point is (%.1lf, %.1lf).\n",randp[k].x,randp[k].y);

    }

}

巴特西

PKU 1379 Run Away(模拟退火算法)

最新文章

热门文章