Problem5298--攀爬者

5298: 攀爬者

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

HKE 考完 GDOI 之后跟他的神犇小伙伴们一起去爬山。他在地形图上标记了 N 个点,每个点 $P_i$ 都有一个坐标 $(x_{i}, y_{i}, z_{i})$。所有点对中,高度值 $z$ 不会相等。HKE 准备从最低的点爬到最高的点,他的攀爬满足以下条件: 
(1) 经过他标记的每一个点;
(2) 从第二个点开始,他经过的每一个点高度 $z$ 都比上一个点高; 
(3) HKE 会飞,他从一个点 $P_i$ 爬到 $P_j$ 的距离为两个点的欧几里得距离。即:$\sqrt{(X_{i} -X_{j})^{2} + (Y_{i} - Y_{j})^{2}+ (Z_{i} - Z_{j})^{2}}$ 
现在,HKE 希望你能求出他攀爬的总距离。

Input

第一行,一个整数 $N$ 表示地图上的点数。
接下来 $N$ 行,三个整数 $x_{i}, y_{i}, z_{i}$ 表示第 $i$ 个点的坐标。
对于 $100\%$ 的数据,$1 \leq N \leq 50000$,答案的范围在 double 范围内。

Output

一个实数,表示 HKE 需要攀爬的总距离(保留三位小数)。

Sample 1 Input

5
2 2 2
1 1 1
4 4 4
3 3 3
5 5 5

Sample 1 Output

6.928

HINT

相同题目:洛谷 P5143

Source/Category

基础算法 4.7.排序