攀爬者
题目背景
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 希望你能求出他攀爬的总距离。
输入格式
第一行,一个整数 \(N\) 表示地图上的点数。
接下来 \(N\) 行,三个整数 \(x_i,y_i,z_i\) 表示第 \(i\) 个点的坐标。
输出格式
一个实数,表示 HKE 需要攀爬的总距离(保留三位小数)
样例 #1
样例输入 #1
5
2 2 2
1 1 1
4 4 4
3 3 3
5 5 5
样例输出 #1
6.928
提示
对于100%的数据,\(1\leq N\leq 50000\),答案的范围在 double 范围内。
2. 题解
2.1 sort函数
思路
排序后计算距离
代码
#include<bits/stdc++.h>
using namespace std;
struct point{
int x;
int y;
int z;
};
bool cmp(point p1, point p2){
return p1.z < p2.z;
}
double getDistance(point p1, point p2){
return sqrt(pow(p1.x - p2.x,2) + pow(p1.y-p2.y, 2) + pow(p1.z - p2.z, 2));
}
int main(){
int n;
cin >> n;
vector<point> p(n);
for(int i = 0; i < n; i++){
cin >> p[i].x >> p[i].y >> p[i].z;
}
sort(p.begin(), p.end(), cmp);
double ans;
for(int i = 0; i < n - 1; i++){
ans += getDistance(p[i], p[i + 1]);
}
printf("%.3lf", ans);
}
标签:p2,p1,point,int,攀爬,P5143,HKE
From: https://www.cnblogs.com/trmbh12/p/18015513