{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"大卫大帝刚刚成为了一个沙漠国家的国王。为了赢得人民的尊重,他决定在全国各地修建水渠,为每个村庄引水。与首都村庄相连的村庄将会得到灌溉。作为国家的统治者和智慧的象征,他需要以最优雅的方式建造这些水渠。\r\u003cbr\u003e\r\u003cbr\u003e经过数天的研究,他终于想出了自己的计划。他希望每英里水渠的平均成本都能最小化。换句话说,水渠的总成本与总长度的比率必须最小化。他只需要建造必要的水渠来为所有村庄引水,这意味着每个村庄与首都之间只会有一条连接方式。\r\u003cbr\u003e\r\u003cbr\u003e他的工程师们勘测了整个国家,并记录了每个村庄的位置和海拔。所有的水渠必须笔直地连接两个村庄,并且是水平建造的。由于每两个村庄的海拔不同,他们得出结论,每两个村庄之间的水渠需要一个垂直的水泵,用于将水抽起或放下。水渠的长度是两个村庄之间的水平距离。水渠的成本是水泵的高度。你应该注意每个村庄的海拔都不同,不同的水渠不能共用一个水泵。水渠可以安全地交叉,并且没有三个村庄共线。\r\u003cbr\u003e\r\u003cbr\u003e作为大卫国王的首席科学家和程序员,你被要求找出最佳的解决方案来建造这些水渠。"}},{"title":"输入","value":{"format":"HTML","content":"有多个测试用例。每个测试用例以包含一个数字 N (2 \u0026lt;\u003d N \u0026lt;\u003d 1000) 的行开始,表示村庄的数量。接下来的 N 行每行包含三个整数 x, y 和 z (0 \u0026lt;\u003d x, y \u0026lt; 10000, 0 \u0026lt;\u003d z \u0026lt; 10000000)。其中 (x, y) 是村庄的位置,z 是海拔。第一个村庄是首都。当 N \u003d 0 时,表示输入结束,不需要处理。"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,输出一个包含小数的行,表示水渠总成本与总长度的最小比率。这个数字应该保留小数点后三位进行四舍五入。"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n0 0 0\r\n0 1 1\r\n1 1 2\r\n1 0 3\r\n0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1.000\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}