POJ2728

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#define ll long long
using namespace std;
const int maxn=1100;
const double eps=1e-6;
struct _node
{
    int x,y,z;
}b[maxn];
struct node
{
    double vi,z;
} a[maxn][maxn];
int n;
bool ha[maxn];
double d[maxn];
inline double dis(int& i,int& j)
{
    return sqrt((b[i].x*1.0-b[j].x)*(b[i].x*1.0-b[j].x)+(b[i].y*1.0-b[j].y)*(b[i].y*1.0-b[j].y));
}

bool check(double mid)
{

    for(int i=1;i<=n;i++)
        d[i]=1e18,ha[i]=false;

    d[1]=0.0;
    double ans=0.0;
    for(int i=1;i<=n;i++)
    {
        int x=0;
        for(int j=1;j<=n;j++)
        {
            if(!ha[j]&&(x==0||d[j]<d[x])) x=j;
        }
        ha[x]=true;
        ans+=d[x];
        for(int i=1;i<=n;i++)
        {
            if(!ha[i]) d[i]=min(d[i],a[x][i].z-a[x][i].vi*mid);
        }
    }
    //cout<<"ans: "<<ans<<endl;
    return ans>0;
}




int main(void)
{
    while(scanf("%d",&n),n)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].z);
        }

        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                a[i][j].vi=dis(i,j);
                a[i][j].z=abs(b[i].z-b[j].z);
            }

        double l=0.0,r=1e9;
        double mid=0.0;
        while(r-l>eps)
        {
            mid=(r+l)/2;
            if(check(mid)) l=mid;
            else r=mid;
        }

        printf("%.3f\n",(l+r)/2);
    }
    return 0;
}