首页 > 代码库 > PKU 1379 Run Away(模拟退火算法)
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=60; const double inf=1e10; const double pi=acos(-1.0); struct Point { double x,y; }p[1010],randp[4]; 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+1; temp.y=rand()%b+1; return temp; } Point Goto_Rand_Dir(double key,Point temp) { double delta=2*pi*(double)rand()/RAND_MAX; temp.x+=key*sin(delta); temp.y+=key*cos(delta); return temp; } int main() { double dis[5]; 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=1;i<=m;i++) scanf("%lf%lf",&p[i].x,&p[i].y); for(i=1;i<=4;i++){//分别往四个方向找四个方向的最小值 dis[i]=inf; randp[i]=Get_Rand_Point(x,y);//给randp[]数组随机取横纵坐标值 for(j=1;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))/2;//关键 while(key>=0.01){//精度要求 for(i=1;i<=4;i++){ for(j=1;j<=shift;j++){ temp=randp[i];//采用之前四个方向确定的随机横纵坐标值 temp=Goto_Rand_Dir(key,temp); if(temp.x<0||temp.y<0||temp.x>x||temp.y>y) continue; now=inf; for(k=1;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=1,k=1;i<=4;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(模拟退火算法)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。