唔。
这道题的火候比较巧妙。
我们是每次找到一个最远的点，然后向那个最远点逼近。
这显然非常合理。
1 #include <cstdlib> 2 #include <cmath> 3 #include <cstdio> 4 #include <algorithm> 5 6 using namespace std; 7 typedef double db; 8 const db eps = 1e-7; 9 const db delta = 0.98; 10 const db INF = 1e100; 11 db random(){ 12 return (rand()&1?1:-1)*rand()*1.0/32767; 13 } 14 struct P3{ 15 db x,y,z; 16 P3 operator + (P3 k1){return (P3){x+k1.x,y+k1.y,z+k1.z};} 17 P3 operator - (P3 k1){return (P3){x-k1.x,y-k1.y,z-k1.z};} 18 P3 operator / (db k1){ return (P3){x/k1,y/k1,z/k1};} 19 P3 operator * (db k1){ return (P3){x*k1,y*k1,z*k1};} 20 db abs(){return sqrt(x*x+y*y+z*z);} 21 }; 22 P3 p[33]; 23 int n; 24 db F(P3 x){ 25 db res=0; 26 for(int i=0;i<n;i++){ 27 res=max(res,(x-p[i]).abs()); 28 } 29 return res; 30 } 31 db SA(){ 32 db t = 100; 33 db ans = INF; 34 P3 x = {0,0,0}; 35 while (t>eps){ 36 db mx = 0;int id=-1; 37 for(int i=0;i<n;i++){ 38 if((x-p[i]).abs()>mx){ 39 mx=(x-p[i]).abs(); 40 id=i; 41 } 42 } 43 ans = min(ans,mx); 44 ans=mx; 45 x=x+(p[id]-x)/mx*t; 46 t*=delta; 47 } 48 printf("%.5f ",ans); 49 } 50 int main(){ 51 while (scanf("%d",&n)&&n){ 52 for(int i=0;i<n;i++){ 53 scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z); 54 } 55 SA(); 56 } 57 }