#501. 「新年欢乐赛 2019」林克上树

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

题目描述

在海拉鲁大陆,树是很常见的,林克也是很常见的。

为了开阔的视野和便于偷袭敌人,想上树的林克也是很常见的。

在上树前,林克会解决树所提出的问题。这种问题,在中文里写作“生成树问题”。

按照惯例,问题交给你来解决。

给出3个点,对于点 i 有3个权值 x_i,y_i,z_i 。点 i 和点 j 之间的连边有2个权值,分别为 a_{ij} b_{ij}

a_{ij}=\sqrt {(x_i-x_j)^2+(y_i-y_j)^2}

b_{ij}=|z_i-z_j|

你需要连接 n-1 条边,得到一棵满足特定条件生成树。

输入格式

第一行读入一个整数 queryType ,若 queryType=1 ,你应输出 \sum a 的最小值;若 queryType=2 ,应输出 \frac {\sum b} {\sum a} 的最小值。

接下来有若干个数据组。每个数据组由一行一个整数 n 开始,接下来 n 行3个整数分别为 n 个点的3个权值 x_i,y_i,z_i

n=0 表示输入结束。

输出格式

对于每组数据,输出一行一个小数,表示答案(保留4位小数)。

样例

样例输入1

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

样例输出1

3.0000

样例输入2

2
8
9 4784 5319528
3078 4430 2554092
7014 4643 5647648
7425 2013 487837
8864 5789 5280332
475 3928 9089381
2759 5047 140647
8586 3248 3580497
7
9647 691 8408082
3998 8837 6883376
5551 4357 1432954
7883 4559 9335924
2182 956 4098149
9983 415 8142475
8520 2460 1563537
0

样例输出2

189.3871
214.9655

数据范围与提示

对于 30\% 的数据:

  • 1 \le n \le 1000
  • queryType=1

对于 50\% 的数据:

  • queryType=1

对于另外 50\% 的数据:

  • queryType=2

对于 100\% 的数据:

  • 1 \le n \le 1500
  • 0 \le x_i,y_i \le 10000
  • 0 \le z_i \le 10000000
  • 8 \le T \le 10 ,其中 T 为数据组数。