本文主要是介绍zoj - 2928 - Mathematical contest in modeling（爬山），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：空间中有 n(3 <= n <= 100) 个点(0.00 <= ai, bi, ci <= 1000.00)，求到这 n 个点的距离之和最短的一点。
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2928
——>>如果是一维的，那么答案是中位数；现在是三维的，赛时不会，赛后学了一种叫做爬山的随机算法用于这题。
爬山算法：先选取其中一值作为最优值，然后向该值附近扫描，若发现更优的值，则以该更优值作为最优值，继续迭代扫描；否则所选值已是最优值。。
此题我以(0, 0, 0)作为初始最优值，然后往其27个可前进方向移动寻找更优值。
精度的设置要特别小心。。1e-8的精度过不了。。
#include <cstdio>
#include <cmath>const int MAXN = 100 + 10;
const int MAXD = 30;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-12;
const double rate = 0.99;int n;
int dx[MAXD];
int dy[MAXD];
int dz[MAXD];
int dcnt;
double a[MAXN];
double b[MAXN];
double c[MAXN];
double A, B, C;void Read()
{for (int i = 0; i < n; ++i){scanf("%lf%lf%lf", a + i, b + i, c + i);}
}void getDirection()
{dcnt = 0;for (int i = -1; i <= 1; ++i){for (int j = -1; j <= 1; ++j){for (int k = -1; k <= 1; ++k){dx[dcnt] = i;dy[dcnt] = j;dz[dcnt] = k;++dcnt;}}}
}int Dcmp(double x)
{if (fabs(x) < EPS) return 0;return x > 0 ? 1 : -1;
}void Solve()
{double step = 1000;double minDistance = INF;A = B = C = 0;getDirection();while (Dcmp(step) != 0){for (int i = 0; i < dcnt; ++i){double newx = A + dx[i] * step;double newy = B + dy[i] * step;double newz = C + dz[i] * step;double sumOfDistance = 0;if (Dcmp(newx) < 0 || Dcmp(newx - 1000) > 0 ||Dcmp(newy) < 0 || Dcmp(newy - 1000) > 0 ||Dcmp(newz) < 0 || Dcmp(newz - 1000) > 0) continue;for (int j = 0; j < n; ++j){sumOfDistance += sqrt((a[j] - newx) * (a[j] - newx) + (b[j] - newy) * (b[j] - newy) + (c[j] - newz) * (c[j] - newz));}if (Dcmp(sumOfDistance - minDistance) < 0){minDistance = sumOfDistance;A = newx;B = newy;C = newz;}}step *= rate;}
}void Output()
{printf("%.3f %.3f %.3f\n", A, B, C);
}int main()
{while (scanf("%d", &n) == 1){Read();Solve();Output();}return 0;
}
这篇关于zoj - 2928 - Mathematical contest in modeling（爬山）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
