题意
给出$n$个点，求出一个点使得到各个点的距离之和最小，距离为欧几里得距离
sol
模拟退火真是玄学，我退了一上午，最后把exp函数去了就a了。
后来改了改，发现是大小符号的问题。。
但是
这样是对的。
然后把rand_max除过去就错了。。
需要改大小号才行。真是玄学。。。
/* */ #include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<ctime> using namespace std; const int maxn = 1e5 + 10; const double eps = 1e-10, 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 = 0; for(int i = 1;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 = 10000; t > eps; t *= dlt) { for(int i = -1; i <= 1; i++) { for(int j = -1; j <= 1; 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 %lfn", 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(19260817); // freopen("a.in", "r", stdin); ans = 1e20; scanf("%d", &n); for(int i = 1; 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[2], yy[2]); //} printf("%d", (int)(ans + 0.5)); return 0; } /* 4 0 0 0 5000 2354 10000 8787 0 */
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/608011.html