首页 > 代码库 > 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;}