题解：P13468 [GCJ 2008 #2] Star Wars

· · 题解

P13468 Star Wars 题解

思路

模拟退火。

题解区清一色的推式子+二分/三分，但是模拟退火也可以通过此题，并且好想，为什么没人用呢？

不知道模拟退火是什么的可以看这里。

首先，我们注意到答案是一个三元函数，所以我们可以选定一个初始点，然后退火逐渐降温，每次随机一个模长小于温度的向量，尝试移动答案，如果更优就移动。但是这样精度不高，所以再随机几轮，取温度恒为 5\times 10^{-7}，提高精度，就可以了。

实测跑得飞快。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const double t = 0.95, eps = 6e-4;
int T, n, x[1005], y[1005], z[1005], p[1005];
pair<double, pair<double, double> > rdm()
{
    double x = rand() * 1145141919, y = rand() * 1145141919, z = rand() * 1145141919; // 利用自然溢出均摊值域
    double l = sqrt(x * x + y * y + z * z);
    return {x / l, {y / l, z / l}};
}
double slv(double x0, double y0, double z0)
{
    double ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans = max(ans, (abs(x[i] - x0) + abs(y[i] - y0) + abs(z[i] - z0)) * 1.0 / p[i]);
    }
    return ans;
}
int main()
{
    srand(time(0));
    cin >> T;
    for (int q = 1; q <= T; q++)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> x[i] >> y[i] >> z[i] >> p[i];
        }
        double nx = 0, ny = 0, nz = 0;
        for (int _ = 1; _ <= 200; _++)
        {
            double tp = 5e4;
            while (tp > eps)
            {
                auto p = rdm();
                double l = 10000ll * rand() * rand() % (ll)(tp * 10000) / 10000.0, ans = slv(nx + p.first * l, ny + p.second.first * l, nz + p.second.second * l);
                if (ans < slv(nx, ny, nz)) nx += p.first * l, ny += p.second.first * l, nz += p.second.second * l;
                tp *= t;
            }
        }
        for (int _ = 1; _ <= 400; _++)
        {
            auto p = rdm();
            double l = 5e-7, ans = slv(nx + p.first * l, ny + p.second.first * l, nz + p.second.second * l);
            if (ans < slv(nx, ny, nz)) nx += p.first * l, ny += p.second.first * l, nz += p.second.second * l;
        }
        printf("Case #%d: %.8f\n", q, slv(nx, ny, nz));
    }
    return 0;
}