1 #include<cstdio> 2 #include<cmath> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 struct Point{double x,y,h;}p[1001]; 7 int n; 8 bool vis[1001]; 9 double DIS[1001][1001],H[1001][1001],map[1001][1001],minn[1001]/*minn[i]存放蓝点i与白点相连的最小边权*/;10 inline double sqr(const double &x){return x*x;}11 inline double dis(const Point &a,const Point &b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}12 inline double prim(const double &rate)13 {14     double sum=0;15     for(int i=1;i<=n;i++)16       for(int j=1;j<=n;j++)17         map[i][j]=H[i][j]-DIS[i][j]*rate;//重设边权 18     memset(vis,false,sizeof(vis));19     memset(minn,0x7f,sizeof(minn));20     minn[1]=0;21     for(int i=1;i<=n;i++)22       {23         int v=0;24         for(int j=1;j<=n;j++)25           if(!vis[j]&&minn[j]<minn[v])26             v=j;27         vis[v]=true;28         for(int j=1;j<=n;j++)29           if(!vis[j])30             minn[j]=min(minn[j],map[v][j]);31       }32     for(int i=1;i<=n;i++)33       sum+=minn[i];34     return sum;35 }36 int main()37 {38     while(1)39       {40           scanf("%d",&n);41           if(!n)42             break;43           for(int i=1;i<=n;i++)44             scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].h);45           for(int i=1;i<=n;i++)46             for(int j=1;j<=n;j++)47               {48                 DIS[i][j]=dis(p[i],p[j]);49                 H[i][j]=fabs(p[i].h-p[j].h);50               }51           double l=0.0,r=100.0;52           while(r-l>0.0000001)//二分比率 53             {54                 double m=(l+r)/2;55                 if(prim(m)>=0)56                   l=m;57                 else58                   r=m;59             }60           printf("%.3f\n",r);61       }62     return 0;63 }