#3471. 沙漠之王 暂未评定

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

大卫大帝刚刚建立了一个沙漠帝国,为了赢得他的人民的尊重,他决定在全国各地建立渠道,为每个村庄提供水源。

与首都相连的村庄将得到水资源的浇灌。

他希望构建的渠道可以实现单位长度的平均成本降至最低。

换句话说,渠道的总成本和总长度的比值能够达到最小。

他只希望建立必要的渠道,为所有的村庄提供水资源,这意味着每个村庄都有且仅有一条路径连接至首都。

他的工程师对所有村庄的地理位置和高度都做了调查,发现所有渠道必须直接在两个村庄之间水平建造。

由于任意两个村庄的高度均不同,所以每个渠道都需要安装一个垂直的升降机,从而使得水能够上升或下降。

建设渠道的成本只跟升降机的高度有关,换句话说只和渠道连接的两个村庄的高度差有关。

需注意,所有村庄(包括首都)的高度都不同,不同渠道之间不能共享升降机。

输入格式

输入包含多组测试数据。

每组测试数据第一行包含整数N,表示村庄(包括首都)的总数目。

接下来N行,每行包含三个整数x,y,z,描述一个村庄的地理位置,(x,y)为该村庄的位置坐标,z为该村庄的地理高度。

第一个被描述的村庄即为首都。

当输入一行为0时,表示输入终止。

输出格式

每组数据输出一个结果,每个结果占一行。

结果为一个保留三位小数的实数,表示渠道的总成本和总长度的比值的最小值。

样例

样例输入

4
0 0 0
0 1 1
1 1 2
1 0 3
0

样例输出

1.000

数据范围与提示

,

,