1 条题解

  • 0
    @ 2025-5-8 11:29:14

    解题思路

    寻找包含所有给定点的最小球体是一个经典的几何优化问题。常用的算法包括:

    迭代逼近法:从一个初始球体开始,逐步调整球心和半径,直到覆盖所有点。

    Welzl's Algorithm:一种随机算法,适用于高维空间的最小包围球计算。

    梯度下降法:通过优化球心和半径,使得所有点到球心的距离的最大值最小化。

    这里我们选择梯度下降法,因为它易于实现且适用于三维空间。

    解题方法

    初始球心:选择所有点的几何中心作为初始球心。

    初始半径:计算球心到最远点的距离作为初始半径。

    迭代优化

    计算当前球心到所有点的距离。

    找到距离最远的点,并调整球心向该点移动一小步。

    重复上述步骤,直到半径的变化小于某个阈值(如1e1e-8)。

    C++代码实现:

    #include <iostream>
    #include<cstdio>
    #include<ctime>
    #include<cmath>
    #include<algorithm>
    #include<cstdlib>
    using namespace std;
    #define N 35
    #define INF 999999
    #define EPS 1e-8
    double a[N],b[N],c[N];
    int main()
    {
        int m;
        while(~scanf("%d",&m)&m)
        {
            for(int i=0;i<m;i++)
            {
                scanf("%lf%lf%lf",&a[i],&b[i],&c[i]);
            }
            double T=100;
            double  ansx=0;
            double ansy=0;
            double  ansz=0;
                int lm=0;
               double ans=INF;
            while(T>EPS)
            {
                  for(int i=0;i<m;++i){
                    if((ansx-a[i])*(ansx-a[i])+(ansy-b[i])*(ansy-b[i])+(ansz-c[i])*(ansz-c[i])>((ansx-a[lm])*(ansx-a[lm])+(ansy-b[lm])*(ansy-b[lm])+(ansz-c[lm])*(ansz-c[lm])))
                        lm=i;
                }
                double d=sqrt((ansx-a[lm])*(ansx-a[lm])+(ansy-b[lm])*(ansy-b[lm])+(ansz-c[lm])*(ansz-c[lm]));
                ans=min(ans,d);
                ansx+=(a[lm]-ansx)/d*T;
                ansy+=(b[lm]-ansy)/d*T;
                ansz+=(c[lm]-ansz)/d*T;
                T=T*0.98;
            }
            printf("%.5f\n",ans);
     
        }
        return 0;
    }
    • 1

    信息

    ID
    1070
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    8
    已通过
    1
    上传者