#P2728. Desert King
Desert King
描述
大卫(David the Great)刚刚成为一个沙漠国家的国王。为了赢得人民的尊敬,他决定在全国各地修建渠道,将水输送到每个村庄。只要与首都村庄相连的村庄就能获得水源。作为国家的最高统治者和智慧的象征,他需要以最优雅的方式建造这些渠道。
经过多日研究,他最终制定了计划:他要使每英里渠道的平均造价最小化。换句话说,要使渠道的总造价与总长度之比最小。他只需修建必要的渠道以覆盖所有村庄,这意味着每个村庄到首都只有一条路径。
工程师们测量了各村庄的位置和海拔。所有渠道都必须在两村庄间直线水平铺设。由于任意两村庄海拔不同,他们决定每条渠道需配备一个垂直水泵,可将水向上提或让水向下流。渠道长度为两村庄的水平距离,渠道造价为水泵高度(即两村庄海拔差的绝对值)。请注意,每个村庄海拔各不相同,不同渠道不能共用同一水泵。渠道可安全相交,且不会有三点共线。
作为国王的高级科学家兼程序员,你的任务是找到最佳方案修建这些渠道。
输入
有若干测试用例。每个测试用例第一行包含一个整数 $N$($2 \le N \le 1000$),表示村庄数量。接下来的 $N$ 行,每行包含三个整数 $x, y, z$($0 \le x,y < 10000,;0 \le z < 10000000$),其中 $(x,y)$ 是村庄的平面坐标,$z$ 是海拔。第一个村庄为首都。当 $N=0$ 时,输入结束,该测试用例不予处理。
输出
对于每个测试用例,输出一行小数,即渠道总造价与总长度之比的最小值,输出时保留三位小数,四舍五入。
输入样例 1
4
0 0 0
0 1 1
1 1 2
1 0 3
0
输出样例 1
1.000
来源
北京 2005