题解 SP34 【RUNAWAY - Run Away】
xukuan
2020-08-04 10:56:30
声明：有参考stogic的题解
**算法：模拟退火**
我来讲一下这题模拟退火的具体思路。
首先得到一个点之后，我们要算出他的值，然后与当前的答案比较，如果这个值较小就接受他，否则以一个递减的概率接受他。
**几个值**
初温：$\frac{the \space length \space of \space the \space board}{\sqrt{n}}$
降温系数：$0.996$
递减的概率：$e^{-\frac{eps}{temperature}}*RAND\_MAX>rand()$
**每次走的方向**
当前走的距离就是当前温度
走的角度随机一个，然后用sin和cos算出长度，要注意，这两个函数里的值是弧度制，所以是$sin(\pi)$而非$sin(180)$
还有就是这题的随机种子一定要足够随机，要srand三次，不然会炸掉
代码：
```cpp
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const double eps=1e-5,INF=1ll<<60,pi=acos(-1);
const ll N=1010;
ll Rx,Ry,n;
double ansx,ansy,ans;
struct{
ll x,y;
}a[N];
inline ll read(){
ll x=0,tmp=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') tmp=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return tmp*x;
}
inline double sqr(double v){
return v*v;
}
inline double calc(double x,double y){
double ans=INF;
for(ll i=1; i<=n; i++) ans=min(ans,sqrt(sqr(x-a[i].x)+sqr(y-a[i].y)));
return ans;
}
inline void SA(){
double x=ansx,y=ansy;
double t=max(Rx,Ry)*1.0/sqrt(n);
while(t>eps){
double angle=(double)(rand()%1000+1)/1000.0*2*pi;
double dex=t*cos(angle),dey=t*sin(angle);
double X=fabs(x+dex),Y=fabs(y+dey);
if(X>=eps&&X<=Rx&&Y>=eps&&Y<=Ry){
double sum=calc(X,Y);
double cha=ans-sum;
if(cha<0){
ans=sum;
ansx=x=X;
ansy=y=Y;
}
else if(exp(-cha/t)*RAND_MAX>rand()){
x=X; y=Y;
}
t*=0.996;
}
}
}
int main(){
srand(19260817);
srand(rand());
srand(rand());
for(ll T=read(); T; T--){
Rx=read(); Ry=read(); n=read();
ll sumx=0,sumy=0;
for(ll i=1; i<=n; i++){
a[i].x=read();
a[i].y=read();
sumx+=a[i].x;
sumy+=a[i].y;
}
ansx=sumx/n; ansy=sumy/n; ans=0;
for(ll i=1; i<=500; i++) SA();
printf("The safest point is (%.1lf, %.1lf).\n",ansx,ansy);
}
return 0;
}
```