POJA Star not a Tree?(模拟退火)

时间：2023-03-09 20:44:12
POJA Star not a Tree?(模拟退火)

题意

题目链接

给出$n$个点，求出一个点使得到各个点的距离之和最小，距离为欧几里得距离

Sol

模拟退火真是玄学，我退了一上午，最后把exp函数去了就A了。

后来改了改，发现是大小符号的问题。。

但是

POJA Star not a Tree?(模拟退火)

这样是对的。

然后把RAND_MAX除过去就错了。。

需要改大小号才行。真是玄学。。。

/*

*/

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<ctime>

using namespace std;

const int MAXN = 1e5 + ;

const double eps = 1e-, Dlt = 0.97;

int N;

double xx[MAXN], yy[MAXN];

double Ans;

double rand(double T, int opt) {

    return opt * T ;

}

double sqr(double x) {

    return x * x;

}

double calc(double x, double y) {

    double ans = ;

    for(int i = ;i <= N; i++)

        ans += sqrt(sqr(x - xx[i]) + sqr(y - yy[i]));

    return ans;

}

void solve(double x, double y) {

    double now = calc(x, y);

    Ans = min(Ans, now);

    for(double T = ; T > eps; T *= Dlt) {

        for(int i = -; i <= ; i++) {

            for(int j = -; j <= ; j++) {

                double wx = x + rand(T, i), wy = y + rand(T, j);

            //    if(wx < 0 || wy < 0 || wx > 10000 || wy > 10000) continue;

                double wv = calc(wx, wy);

            //    printf("%lf %lf %lf\n", wx, wy, calc(wx, wy));

                if(wv < Ans) x = wx, y = wy, Ans= wv;

                if(wv < now || ( exp((now - wv) / T) < (rand() / RAND_MAX) )) x = wx, y = wy, now = wv;

            //    if(wv < now) x = wx, y = wy, now = wv;

            }

        }

    }

}

int main() {

    srand();

//    freopen("a.in", "r", stdin);

    Ans = 1e20;

    scanf("%d", &N);

    for(int i = ; i <= N; i++)

        scanf("%lf %lf", &xx[i], &yy[i]);

    //printf("%lf", calc(5000, 5000));

    //for(int i = 1; i <= N; i++) {

    //    double x = rand() % 10000, y = rand() % 10000;

        solve(xx[], yy[]);

    //}

    printf("%d", (int)(Ans + 0.5));

    return ;

}

/*

4

0 0

0 5000

2354 10000

8787 0

*/

相关文章