数据过弱,建议加强(爬山法能过)
查看原帖
数据过弱,建议加强(爬山法能过)
524085
yanbinmu楼主2024/11/28 15:40

如题,曾经将代码写为了:

else if(exp( - DE / T) > rand() % RAND_MAX)

然后 AC 了……

#include <bits/stdc++.h>
using namespace std;
double X, Y;
int n;
int x[1005], y[1005];

double dis(double x1, double y1, double x2, double y2){
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

double calc(double a, double b){
    double minn = 0x7fffffff;
    for(int i = 1;i <= n;i ++ ){
        minn = min(minn, dis(a, b, 1.0 * x[i], 1.0 * y[i]));
    }
    return minn;
}

double rrand(double l, double r){
    if(l > r) swap(l, r);
    return rand() * (r - l) / RAND_MAX + l;
}

const double delta = 0.997;
double p, q, ans;
double a, b;
void SA(){
    double T = 100000;
    while(T > 1e-12){
        double new_x = rrand(max(0.0, p - T), min(X, p + T));
        double new_y = rrand(max(0.0, q - T), min(Y, q + T));
        double new_ans = calc(new_x, new_y);
        double DE = ans - new_ans;
        if(DE < 0){
            ans = new_ans;
            p = new_x;
            q = new_y;
            a = p;
            b = q;
        }
//        else if(exp( - DE / T) * RAND_MAX> rand()){
//            p = new_x;
//            q = new_y;
//        }
        T *= delta;
    }
}
int main(){
    srand(rand());
    int T;
    scanf("%d", &T);
    while(T -- ){
        scanf("%lf %lf %d", &X, &Y, &n);
        for(int i = 1;i <= n;i ++ ){
            scanf("%d %d", &x[i], &y[i]);
        }
        a = rrand(0, X);
        b = rrand(0, Y);
        ans = calc(a, b);
        // cout<<ans<<endl;
        for(int i = 1;i <= 10;i ++ ) SA();
//        while(clock() < 0.9 * CLOCK_PER_SEC) SA();
        printf("The safest point is (%.1lf, %.1lf).\n", a, b);
    }
    return 0;
}
2024/11/28 15:40
加载中...