题意:给你100个三维空间里的点,让你求一个点,使得他到所有点距离最大的值最小,也就是让你找一个最小的球覆盖掉这n个点
题解:红书模板题,这题也因为数据小,精度也不高,所以也可以用随机算法,模拟退火之类的
#include<bits/stdc++.h>
using namespace std;
int npoint,nouter;
struct Tpoint
{
double x,y,z;
};
Tpoint pt[],outer[],res;
#define eps 1e-9
double radius,tmp;
inline double dist(Tpoint p1,Tpoint p2)
{
double dx=p1.x-p2.x,dy=p1.y-p2.y,dz=p1.z-p2.z;
return (dx*dx+dy*dy+dz*dz);
}
inline double dot(Tpoint p1,Tpoint p2)
{
return p1.x*p2.x+p1.y*p2.y+p1.z*p2.z;
}
void ball()
{
Tpoint q[];
double m[][],sol[],L[],det;
int i,j;
res.x=res.y=res.z=radius=;
switch (nouter)
{
case :res=outer[];break;
case :
res.x=(outer[].x+outer[].x)/;
res.y=(outer[].y+outer[].y)/;
res.z=(outer[].z+outer[].z)/;
radius=dist(res,outer[]);
break;
case :
for (int i=;i<;i++)
{
q[i].x=outer[i+].x-outer[].x;
q[i].y=outer[i+].y-outer[].y;
q[i].z=outer[i+].z-outer[].z;
}
for (int i=;i<;i++)
for (int j=;j<;j++)
m[i][j]=dot(q[i],q[j])*;
for (int i=;i<;i++) sol[i]=dot(q[i],q[i]);
if (fabs(det=m[][]*m[][]-m[][]*m[][])<eps) return;
L[]=(sol[] * m[][] - sol[] * m[][])/det;
L[]=(sol[] * m[][] - sol[] * m[][])/det;
res.x=outer[].x+q[].x*L[]+q[].x*L[];
res.y=outer[].y+q[].y*L[]+q[].y*L[];
res.z=outer[].z+q[].z*L[]+q[].z*L[];
radius=dist(res,outer[]);
break;
case :
for (int i=;i<;i++)
{
q[i].x=outer[i+].x-outer[].x;
q[i].y=outer[i+].y-outer[].y;
q[i].z=outer[i+].z-outer[].z;
sol[i]=dot(q[i],q[i]);
}
for (int i=;i<;i++)
for (int j=;j<;j++) m[i][j]=dot(q[i],q[j])*;
det=m[][]*m[][]*m[][]
+m[][]*m[][]*m[][]
+m[][]*m[][]*m[][]
-m[][]*m[][]*m[][]
-m[][]*m[][]*m[][]
-m[][]*m[][]*m[][];
if (fabs(det)<eps) return ;
for (int j=;j<;j++)
{
for (int i=;i<;i++)
m[i][j]=sol[i];
L[j]=( m[][]*m[][]*m[][]
+m[][]*m[][]*m[][]
+m[][]*m[][]*m[][]
-m[][]*m[][]*m[][]
-m[][]*m[][]*m[][]
-m[][]*m[][]*m[][]
)/det;
for (int i=;i<;i++)
m[i][j]=dot(q[i],q[j])*;
}
res=outer[];
for (int i=;i<;i++)
{
res.x+=q[i].x*L[i];
res.y+=q[i].y*L[i];
res.z+=q[i].z*L[i];
}
radius=dist(res,outer[]);
}
}
void minball(int n)
{
ball();
if (nouter<)
{
for (int i=;i<n;i++)
if (dist(res,pt[i])-radius>eps)
{
outer[nouter]=pt[i];
++nouter;
minball(i);
--nouter;
if (i>)
{
Tpoint Tt=pt[i];
memmove(&pt[],&pt[],sizeof(Tpoint)*i);
pt[]=Tt;
}
}
}
}
int main()
{
radius=-;
scanf("%d",&npoint);
for (int i=;i<npoint;i++)
{
scanf("%lf%lf%lf",&pt[i].x,&pt[i].y,&pt[i].z);
}
for (int i=;i<npoint;i++)
if (dist(res,pt[i])-radius>eps)
{
nouter=;
outer[]=pt[i];
minball(i);
}
printf("%.10lf\n",sqrt(radius));
}