最小球覆盖板子

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <math.h>
 4 using namespace std;
 5 const int MAXN=105;
 6 const double EPS=1e-8;
 7 struct Point{
 8     double x,y,z;
 9     Point(double _x=0,double _y=0,double _z=0){
10         x=_x;y=_y;z=_z;
11     }
12 };
13 Point Dots[MAXN];
14 int n;
15  
16 double Distance(Point a,Point b){
17     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));
18 }
19 double Solve(){
20     double Step=100000,ans=1e9,mt;
21     Point z=Point(0.0,0.0,0.0);
22     int s=0;
23     while(Step>EPS){
24         for(int i=1;i<=n;++i){
25             if(Distance(z,Dots[s])<Distance(z,Dots[i])){
26                 s=i;
27             }
28         }
29         mt=Distance(z,Dots[s]);
30         ans=min(ans,mt);
31         z.x+=(Dots[s].x-z.x)/mt*Step;
32         z.y+=(Dots[s].y-z.y)/mt*Step;
33         z.z+=(Dots[s].z-z.z)/mt*Step;
34         Step*=0.98;
35     }return ans;
36 }
37 int main(){
38 
39         scanf("%d",&n);
40         
41         for(int i=1;i<=n;++i){
42             double x,y,z;scanf("%lf%lf%lf",&x,&y,&z);
43             Dots[i]=Point(x,y,z);
44         }
45         printf("%.15f",Solve());
46     
47 }