J12 习题-5 秦始皇修皇陵

题目描述

在中国古代的战国时期（公元前476年至公元前221年），中国有七个国家----，它们是齐、楚、燕、韩、赵、魏和秦。嬴政是秦国的国王。通过9年的战争，他最终征服了其他六个国家，并在公元前221年成为统一中国的第一个皇帝。这就是秦朝----，中国的第一个皇朝（不要与清朝混淆，清朝是中国的最后一个朝代）。所以嬴政给自己取名 "秦始皇"，因为 "始皇 "在中文里是 "第一个皇帝 "的意思。

秦始皇进行了巨大的工程，包括第一个版本的中国长城，现在著名的城市大小的陵墓，由真人大小的兵马俑守卫，以及一个巨大的国家道路系统。关于这个道路系统有一个故事：

中国有 $n$ 个城市，秦始皇希望它们都被 $n-1$ 条道路连接起来，以便他能从首都咸阳前往每个城市。

虽然秦始皇是个暴君，但他希望所有道路的总长度是最小的，这样道路系统就不会造成太多人的死亡。一个叫徐福的道士告诉秦始皇，他可以用法术修路，而且法术修路不花钱也不花力。但徐福只能为秦始皇修一条魔道。因此，秦始皇必须决定在哪里修筑这条魔道。秦始皇希望所有非魔法道路的总长度越小越好，但徐福希望魔法道路能让尽可能多的人受益----，所以秦始皇决定 $A/B$（A与B的比例）的值必须是最大的，其中 $A$ 是魔法道路连接的两个城市的总人口，$B$ 是非魔法道路的总长度。

你会帮助秦始皇吗？一个城市可以被看作是一个点，一条路可以被看作是连接两点的线段。

输入格式

第一行包含一个整数 $t$，意味着有 $t$ 个测试案例。 对于每个测试案例： 第一行是一个整数 $n$，意味着有 $n$ 个城市。 接着是 $n$ 行。每行包含三个整数 $X$、$Y$ 和 $P$。$(X, Y)$ 是一个城市的坐标，$P$ 是该城市的人口。 可以保证每个城市都有一个不同的位置。

输出格式

对于每个测试案例，打印一行表示上述的最大比率 $A/B$。结果应四舍五入到小数点后的 $2$ 位数。

样例输入

2
4
1 1 20
1 2 30
200 2 80
200 1 100
3
1 1 20
1 2 30
2 2 40

样例输出

65.00
70.00

样例解析

第一组数据，$1$ 号城市连接 $2$ 号城市，$2$ 号城市连接 $3$ 号城市，$3$ 号城市连接 $4$ 号城市，$2$ 号城市到 $3$ 号城市的道路是魔法道路，即人口数 $A=100+30=130$，除去魔法道路后总之为 $B=1+1=2$，所以最大比率是 $130/2=65$。

数据范围

对于 $100 \%$ 的数据：$t \le 10$ ，$2 \le n \le 1000$ ，$0 \le X, Y \le 1000$，$0 < P < 100000$。