NanjingOnsite:三维坐标下给出 \(n\) 个点 \(p_i\)，找到一个点 \(best\) 使得 \(max_{i=1}^ndis(best,p_i)\) 最小，\(n\le 100\)

最小球覆盖呵呵

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 103;
const double PI = acos(-1);
const double EPS = 1e-6;
int n;
double ans;
struct Point{
    double x,y,z;
}p[MAXN],now,best;
double dis(Point &a,Point &b){
    return sqrt(
        (a.x-b.x)*(a.x-b.x)
        +(a.y-b.y)*(a.y-b.y)
        +(a.z-b.z)*(a.z-b.z)
    );
}
double rand01(){
    return (rand()%1000+1.0)/1000.0;
}
double lambda(Point cur){
    double res=0;
    for(int i=1;i<=n;i++){
        res=max(dis(cur,p[i]),res);
    }
    if(res<ans) best=cur,ans=res;
    return res;
}
int main(){
    //freopen("stdin.txt","r",stdin);
    srand(19260817);
    while(~scanf("%d",&n)){
        double nx=0,ny=0,nz=0;
        for(int i=1;i<=n;i++){
            scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z);
            nx+=p[i].x/n;
            ny+=p[i].y/n;
            nz+=p[i].z/n;
        }
        best=now=(Point){nx,ny,nz};ans=0;
        for(int i=1;i<=n;i++){
            ans=max(ans,dis(best,p[i]));
        }
        double T=2e6;
        while(T>EPS){
            double dx=now.x+T*(rand01()*2-1);
            double dy=now.y+T*(rand01()*2-1);
            double dz=now.z+T*(rand01()*2-1);
            Point tmp=(Point){dx,dy,dz};
            double t1=lambda(now),t2=lambda(tmp);
            double de=t1-t2;
            if(de>=0||exp(de/T)>=rand01()){
                now=tmp;
            }
            T*=0.99;
        }
        int times=2e6;
        while(times--){
            double dx=best.x+rand01()*(rand01()*2-1);
            double dy=best.y+rand01()*(rand01()*2-1);
            double dz=best.z+rand01()*(rand01()*2-1);
            lambda((Point){dx,dy,dz});
        }
        printf("%.5lf\n",lambda(best));
    }
    return 0;
}