模拟退火求调(玄关)
查看原帖
模拟退火求调(玄关)
804607
rainygame楼主2023/11/4 13:41

参数和第一篇题解基本相同,为啥样例还是找不到最优解?

代码:

#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;
}

2023/11/4 13:41
加载中...