模拟退火算法。
随机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;
}