参数和第一篇题解基本相同,为啥样例还是找不到最优解?
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 1001
mt19937 rnd(time(0));
const int d(0.9997);
int t, m;
double X, Y, ans, nowx, nowy;
double x[MAXN], y[MAXN];
double ansx, ansy;
double g(){
return (double)rnd() / UINT_MAX;
}
double f(double l, double r){
if (l > r) swap(l, r);
return g() * (r-l) + l;
}
double get_minn(double X, double Y){
double res(1e18);
for (int i(1); i<=m; ++i) res = min(res, sqrt(pow(X-x[i], 2)+pow(Y-y[i], 2)));
return res;
}
void SA(){
double t(1e5);
while (t > 1e-6){
double nx(f(max(nowx-t, 0.0), min(nowx+t, X))), ny(f(max(nowy-t, 0.0), min(nowy+t, Y)));
double dis(get_minn(nx, ny)), delta(ans-dis);
if (delta <= 0.0){
ans = dis;
nowx = ansx = nx;
nowy = ansy = ny;
}else if (exp(-delta/t) > g()){
nowx = nx;
nowy = ny;
}
t *= d;
}
}
signed main(){
cin >> t;
while (t--){
cin >> X >> Y >> m;
for (int i(1); i<=m; ++i) cin >> x[i] >> y[i];
nowx = ansx = f(0, X);
nowy = ansy = f(0, Y);
ans = get_minn(ansx, ansy);
for (int i(1); i<=1000; ++i) SA();
printf("The safest point is (%.1lf, %.1lf).\n", ansx, ansy);
}
return 0;
}