题目链接：BZOJ 3680

给出平面中的 $n$ 个点，求这 $n$ 个点的带权类费马点（费马点：在三角形内到各个顶点距离之和最小的点）。

数据范围：$1 \le n \le 10 ^ 4$。

Solution

显然此题可以用爬山算法或者模拟退火求解。

具体实现详见「算法笔记」模拟退火

时间复杂度：$\mathcal O(\text{???})$ 。

Code

爬山算法：

#include <cstdio>
#include <cmath>

const int N = 1e4 + 5;

int n, x[N], y[N], w[N];
double ansx, ansy;

void hillClimb() {
    double t = 1000;
    while (t > 1e-8) {
        double nowx = 0, nowy = 0;
        for (int i = 1; i <= n; i++) {
            double dx = x[i] - ansx, dy = y[i] - ansy;
            double dis = sqrt(dx * dx + dy * dy);
            nowx += (x[i] - ansx) * w[i] / dis;
            nowy += (y[i] - ansy) * w[i] / dis;
        }
        ansx += nowx * t, ansy += nowy * t;
        t *= (t > 0.5 ? 0.5 : 0.97);
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &x[i], &y[i], &w[i]);
        ansx += x[i], ansy += y[i];
    }
    ansx /= n, ansy /= n;
    hillClimb();
    printf("%.3lf %.3lf\n", ansx, ansy);
    return 0;
}

模拟退火：

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

const int N = 1e4 + 5;

int n, x[N], y[N], w[N];
double ansx, ansy, dis;

double Rand() {
    return (double)rand() / RAND_MAX;
}
double calc(double xx, double yy) {
    double res = 0;
    for (int i = 1; i <= n; i++) {
        double dx = x[i] - xx, dy = y[i] - yy;
        res += sqrt(dx * dx + dy * dy) * w[i];
    }
    if (res < dis) dis = res, ansx = xx, ansy = yy;
    return res;
}
void simulateAnneal() {
    double t = 1e5;
    double nowx = ansx, nowy = ansy;
    while (t > 1e-3) {
        double nxtx = nowx + t * (Rand() * 2 - 1);
        double nxty = nowy + t * (Rand() * 2 - 1);
        double delta = calc(nxtx, nxty) - calc(nowx, nowy);
        if (exp(-delta / t) > Rand()) {
            nowx = nxtx, nowy = nxty;
        }
        t *= 0.97;
    }
    for (int i = 1; i <= 1000; i++) {
        double nxtx = ansx + t * (Rand() * 2 - 1);
        double nxty = ansy + t * (Rand() * 2 - 1);
        calc(nxtx, nxty);
    }
}
int main() {
    srand(time(0) + *(new char));
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &x[i], &y[i], &w[i]);
        ansx += x[i], ansy += y[i];
    }
    ansx /= n, ansy /= n, dis = calc(ansx, ansy);
    simulateAnneal();
    printf("%.3lf %.3lf\n", ansx, ansy);
    return 0;
}