跳到主要内容
图灵 OJTURING / ONLINE JUDGE

F. 攀爬者

  • 传统题
  • 1000ms
  • 125MiB

攀爬者

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

HKE 考完 GDOI 之后跟他的神犇小伙伴们一起去爬山。

题目描述

HKE 在地形图上标记了 NN 个点,每个点 PiP_i 都有一个坐标 (xi,yi,zi)(x_i,y_i,z_i),且在所有点对中,高度值 zz 不会相等。HKE 准备从最低的点爬到最高的点,他的攀爬满足以下条件:

  1. 经过他标记的每一个点;
  2. 从第二个点开始,他经过的每一个点高度 zz 都比上一个点高;
  3. HKE 会飞,他从一个点 PiP_i 爬到 PjP_j 的距离为两个点的欧几里得距离,即 (Xi−Xj)2+(Yi−Yj)2+(Zi−Zj)2\sqrt{(X_i-X_j)^2+(Y_i-Y_j)^2+(Z_i-Z_j)^2}。

现在,HKE 希望你能求出他攀爬的总距离。

输入格式

第一行,一个整数 NN 表示地图上的点数。

接下来 NN 行,每行三个整数 xi,yi,zix_i,y_i,z_i,表示第 ii 个点的坐标。

输出格式

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

样例 1

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

说明 / 提示

对于 100%100\% 的数据,1≤N≤500001\leq N\leq 50000,答案在 double 类型的表示范围内。


来源:洛谷 P5143。题面及样例来自洛谷公开题库导出,保留原题署名。

本题在 Turing OJ 内提交评测;测试数据由本站独立构造,并非洛谷原始测试点。

排序&&二分

未参加
状态
已结束
规则
XCPC
题目
6
开始于
2026-10-15 18:00
结束于
2026-10-15 23:00
持续时间
5 小时
主持人
参赛人数
25