首页 > 代码库 > POJ 1379
POJ 1379
模拟退火算法。
随机MAX个点,然后,退火移动,选取距离所有点中最短中最长者即可。理解和我上一篇一样。
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <time.h>using namespace std;const int MAXN=1010;const int MAX=50;const double inf=1e10;const double eps=1e-3;struct point { double x,y;};point p[MAXN]; point tar[MAX];double best[MAXN];int n; double ans_dis; point s,tp; double tmp_dis;double X,Y;double getdouble(){ double ret=((rand()*rand())%1000000)*1.0/1e6; return ret;}double dist(point &u,point &v){ return sqrt((u.x-v.x)*(u.x-v.x)+(u.y-v.y)*(u.y-v.y)); }double work(point &t){ double ret=inf; for(int i=0;i<n;i++){ double tmp=dist(t,p[i]); ret=min(ret,tmp); } return ret;}int main(){ int cas; bool flag; scanf("%d",&cas); srand(time(0)); while(cas--){ scanf("%lf%lf%d",&X,&Y,&n); for(int i=0;i<n;i++){ scanf("%lf%lf",&p[i].x,&p[i].y); } for(int i=0;i<MAX;i++){ tar[i].x=getdouble()*X; tar[i].y=getdouble()*Y; best[i]=work(tar[i]); } double T=100; for(double t=T;t>eps;t*=0.8){ for(int i=0;i<MAX;i++){ for(int j=0;j<30;j++){ double tmp=getdouble(); if(rand()&1) tmp*=-1; tp.x=tar[i].x+tmp*t; tmp=getdouble(); if(rand()&1) tmp*=-1; tp.y=tar[i].y+tmp*t; if(tp.y>=0&&tp.y<Y&&tp.x>=0&&tp.x<=X){ double f=work(tp); if(f>best[i]) { tar[i]=tp; best[i]=f; } } } } } ans_dis=best[0]; for(int i=0;i<MAX;i++){ double fe=best[i]; if(fe>ans_dis){ s=tar[i]; ans_dis=fe; } } printf("The safest point is (%.1lf, %.1lf).\n",s.x,s.y); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。