1. 题目

传送门= ̄ω ̄=

2. 题解

本来是做 BZOJ 的最小求覆盖问题的,但是那题似乎 SPJ 有问题 A 不掉就来做这题了。

实际上可以用随机增量法做,可以做到 $O(n)$,但是求四个点的外接球有点太过麻烦,因此爬山即可

先随机一个球心位置,然后每次找到距离当前球心最远的点,它们之间的距离就是球的半径,然后把球心往该点方向移动,步长逐渐减小即可。

数据非常小,随便瞎搞都能过。。。

代码:

#include <cstdio>
#include <cmath>

#define NS (35)
#define PW2(a) ((a) * (a))

using namespace std;

int n;

double X[NS], Y[NS], Z[NS];

double Range(double x1, double y1, double z1, double x2, double y2, double z2)
{
    return PW2(x1 - x2) + PW2(y1 - y2) + PW2(z1 - z2);
}

int main(int argc, char const* argv[])
{
    while (scanf("%d", &n), n)
    {
        for (int i = 1; i <= n; i += 1)
            scanf("%lf%lf%lf", &X[i], &Y[i], &Z[i]);
        double S = 1, x = X[1], y = Y[1], z = Z[1], r = 0;
        for (int C = 1; C <= 2000; C += 1, S *= 0.99)
        {
            double mx = 0, tmp; int mi = 0;
            for (int i = 1; i <= n; i += 1)
                if (tmp = Range(x, y, z, X[i], Y[i], Z[i]), tmp > mx)
                    mx = tmp, mi = i;
            x += S * (X[mi] - x), y += S * (Y[mi] - y), z += S * (Z[mi] - z);
            r = mx;
        }
        printf("%.5f\n", sqrt(r));
    }
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注