Country Meow（三分套三分套三分 && 模拟退火）

Country Meow（三分套三分套三分 && 模拟退火）

题目链接（D题）

题目大意：

三维空间中，给定 $N$ 个点，求最小球覆盖。输出半径

**解法一： ** 模拟退火

先确定一个点作为圆心，每次向距离它最远的点以某一概率靠近。越到后面，温度越低，跳跃越来越不随机，最终逼近答案。

太妙啊

#include<bits/stdc++.h>

using namespace std;

const int N = 110; 
const double rate = 0.98;  //降温系数
const double eps = 1e-3;   //精度
const double start_T = 1000.0; //初始温度
struct Point{
    double x, y, z;
}p[N];
int n;
double ppow(double x) {
    return x * x;
}
double dis(Point a, Point b) {
    return sqrt(ppow(a.x - b.x) + ppow(a.y - b.y) + ppow(a.z - b.z));
}

double simulateAnneal() {
    double T = start_T;
    Point tp = {0, 0, 0};  //先确定一个答案点
    double ans = 1e99;     //半径

    while (T > eps) {
        Point xp = p[1];
        for (int i = 2; i <= n; i++) {  //找到距离当前的点最远的点
            if (dis(tp, p[i]) > dis(tp, xp)) {
                xp = p[i];
            }
        }
        ans = min(ans, dis(xp, tp));  
        tp.x += (T / start_T) * (xp.x - tp.x);  
        tp.y += (T / start_T) * (xp.y - tp.y);
        tp.z += (T / start_T) * (xp.z - tp.z);
        T *= rate;  //降温
    }
    return ans;
}

int main () {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lf%lf%lf", &p[i].x, &p[i].y, &p[i].z);
    printf("%.15f\n", simulateAnneal());

    return 0;
}

解法二： 三分套三分套三分

我只能爬…

三维，每一维都是单峰函数，三个三分套一下就行了。

#include<bits/stdc++.h>

using namespace std;

const int N = 110;
const double eps = 1e-3;
struct Point{
    double x, y, z;
    Point () {x = y = z = 0; }
    Point (double _x, double _y, double _z) {
        x = _x; y = _y; z = _z;
    }
    Point operator + (const Point& p) {
        return Point(x + p.x, y + p.y, z + p.z);
    }
    Point operator - (const Point& p) {
        return Point(x - p.x, y - p.y, z - p.z);
    }
    double len() {
        return sqrt(x * x + y * y + z * z);
    }
}p[N];
int n;

double cal3(double x, double y, double z) {
    double res = 0;
    for (int i = 1; i <= n; i++) {
        res = max(res, (p[i] - Point(x, y, z)).len());
    }
    return res;
}

double cal2(double x, double y) { //三分第三维
    double res = 1e18;
    double l = -100000.0, r = 100000.0;
    while (r - l > eps) {
        double m1 = l + (r - l) / 3.0;
        double m2 = l + (r - l) / 3.0 * 2.0;
        double res1 = cal3(x, y, m1), res2 = cal3(x, y, m2);
        res = min(res, min(res1, res2));
        if (res1 < res2) r = m2;
        else l = m1;
    }
    return res;
}

double cal1(double x) {    //三分二维
    double res = 1e18;
    double l = -100000.0, r = 100000.0;
    while (r - l > eps) {
        double m1 = l + (r - l) / 3.0;
        double m2 = l + (r - l) / 3.0 * 2.0;
        double res1 = cal2(x, m1), res2 = cal2(x, m2);
        res = min(res, min(res1, res2));
        if (res1 < res2) r = m2;
        else l = m1;
    }
    return res;
}

int main () {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lf%lf%lf", &p[i].x, &p[i].y, &p[i].z);
    double res = 1e18;
    double l = -100000.0, r = 100000.0; 
    while (r - l > eps) {    //三分第一维
        double m1 = l + (r - l) / 3.0;
        double m2 = l + (r - l) / 3.0 * 2.0;
        double res1 = cal1(m1), res2 = cal1(m2);
        res = min(res, min(res1, res2));
        if (res1 < res2) r = m2;
        else l = m1;
    }
    printf("%.15f\n", res);
    return 0;
}