只是套了个模板，模拟退火具体的过程真心不懂阿
1 //#pragma comment(linker, "/STACK:16777216") //for c++ Compiler 2 #include <stdio.h> 3 #include <iostream> 4 #include <cstring> 5 #include <cmath> 6 #include <stack> 7 #include <queue> 8 #include <vector> 9 #include <algorithm> 10 #define ll long long 11 #define Max(a,b) (((a) > (b)) ? (a) : (b)) 12 #define Min(a,b) (((a) < (b)) ? (a) : (b)) 13 #define Abs(x) (((x) > 0) ? (x) : (-(x))) 14 using namespace std; 15 16 const int INF = 0x3f3f3f3f; 17 const int MAXN = 220; 18 const double eps = 1e-8; 19 int n; 20 struct POINT{ 21 double x,y,z; 22 }ps[35],q; 23 24 double dist(POINT a,POINT b){ 25 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)); 26 } 27 28 int maxD(POINT p){ 29 double res = 0; 30 int i, k = 0; 31 for(i = 0; i < n ; ++i){ 32 double tmp = dist(p,ps[i]); 33 if(tmp > res){ 34 k = i; 35 res = dist(p,ps[i]); 36 } 37 } 38 return k; 39 } 40 41 double BallCover(){ 42 double step = 100, ans = INF; 43 q.x = q.y = q.z = 0.0; 44 while(step > eps){ 45 int d = maxD(q); 46 double tmp = dist(ps[d],q); 47 if(tmp < ans) ans=tmp; 48 double dx = ps[d].x - q.x; 49 double dy = ps[d].y - q.y; 50 double dz = ps[d].z - q.z; 51 dx /= tmp; 52 dy /= tmp; 53 dz /= tmp; 54 q.x += (dx*step); 55 q.y += (dy*step); 56 q.z += (dz*step); 57 step *= 0.98; 58 } 59 return ans; 60 } 61 62 int main(){ 63 int i; 64 while(EOF != scanf("%d",&n)){ 65 if(0 == n) break; 66 for(i = 0; i < n ; ++i) 67 scanf("%lf%lf%lf",&ps[i].x,&ps[i].y,&ps[i].z); 68 printf("%.5f ",BallCover()); 69 } 70 return 0; 71 }