显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<ctime>
#include<cmath>
using namespace std;
#define sqr(x) (x)*(x)
const int SIZEN=1010;
const double INF=1e10,pi=acos(-1.0),eps=1e-7;
class POINT{
public:
double x,y;
double d;
};
int random(int x,int y){
return rand()%(y-x+1)+x;
}
double random_real(void){//生成一个[0,1]内的实数
return ((((rand()<<15)|rand())&0x3fffffff)+0.0)/(0x3fffffff+0.0);
}
double W,H;
int N;
POINT hole[SIZEN];
POINT P[SIZEN];
double dist(POINT a,POINT b){
return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
double calc(POINT a){
if(a.x<0||a.x>W||a.y<0||a.y>H) return -INF;
double ans=INF;
for(int i=1;i<=N;i++) ans=min(ans,dist(a,hole[i]));
return ans;
}
void jump(POINT &a,double r,double T){//点为a,步长为r,温度为T
double alpha=random(0,359)/180.0*pi;
POINT b;//在以a为圆心,r为半径的圆上随机一个点b
b.x=a.x+r*cos(alpha),b.y=a.y+r*sin(alpha);
if(b.x<0||b.x>W||b.y<0||b.y>H) return;//如果b不合法
b.d=calc(b);
if(b.d>a.d) a=b;//如果比当前解优,直接接受
else{//否则以概率e^(-△/T)接受这个解
double p=exp(-(a.d-b.d)/T);
if(random_real()<=p) a=b;
}
}
void SA(void){
int n=20;//点的数量
/*模拟退火算法具有并行性,可以从一组初始点开始同时运行,
使最终的解更优*/
double T=1000.0;//初始温度
double delta=max(W,H)/sqrt(n+0.0);//初始步长
int rep=30;//同一温度迭代30次
for(int i=1;i<=n;i++){//初始点均由随机生成
P[i].x=random(0,W);
P[i].y=random(0,H);
P[i].d=calc(P[i]);
}
while(delta>eps){
for(int i=1;i<=n;i++){
for(int j=1;j<=rep;j++) jump(P[i],delta,T);
}
delta*=0.9,T*=0.8;
}
int ans=1;
for(int i=2;i<=n;i++) if(P[i].d>P[ans].d) ans=i;
printf("The safest point is (%.1lf, %.1lf).\n",P[ans].x,P[ans].y);
}
void read(void){
scanf("%lf%lf%d",&W,&H,&N);
for(int i=1;i<=N;i++) scanf("%lf%lf",&hole[i].x,&hole[i].y);
}
int main(){
freopen("runaway.in","r",stdin);
freopen("runaway.out","w",stdout);
srand(time(0));
int T;//原题是ACM赛制,有多组数据
//scanf("%d",&T);
T=1;
while(T--){
read();
SA();
}
return 0;
}
cstdio