网上做论文的网站,天津高端网站建设,邮箱163登录,营销型外贸网站建设公司攀爬者
题目描述
他在地形图上标记了 N N N 个点#xff0c;每个点 P i P_i Pi 都有一个坐标 ( x i , y i , z i ) (x_i,y_i,z_i) (xi,yi,zi)。所有点对中#xff0c;高度值 z z z 不会相等。HKE 准备从最低的点爬到最高的点#xff0c;他的攀爬满足以下条件每个点 P i P_i Pi 都有一个坐标 ( x i , y i , z i ) (x_i,y_i,z_i) (xi,yi,zi)。所有点对中高度值 z z z 不会相等。HKE 准备从最低的点爬到最高的点他的攀爬满足以下条件
(1) 经过他标记的每一个点
(2) 从第二个点开始他经过的每一个点高度 z z z 都比上一个点高
(3) HKE 会飞他从一个点 P i P_i Pi 爬到 P j P_j Pj 的距离为两个点的欧几里得距离。即 ( X i − X j ) 2 ( Y i − Y j ) 2 ( Z i − Z j ) 2 \sqrt{(X_i-X_j)^2(Y_i-Y_j)^2(Z_i-Z_j)^2} (Xi−Xj)2(Yi−Yj)2(Zi−Zj)2
现在HKE 希望你能求出他攀爬的总距离。
输入格式
第一行一个整数 N N N 表示地图上的点数。
接下来 N N N 行三个整数 x i , y i , z i x_i,y_i,z_i xi,yi,zi 表示第 i 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 ≤ N ≤ 50000 1\leq N\leq 50000 1≤N≤50000答案的范围在 double 范围内。
原题
洛谷P5143——传送门
代码
#include bits/stdc.h
using namespace std;
#define max_Heap(x) priority_queuex, vectorx, lessx
#define min_Heap(x) priority_queuex, vectorx, greaterx
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
typedef pairlong long, long long PLL;
const double PI acos(-1);struct node
{double x, y, z; // 由于距离为小数所以用double存储坐标可以方便运算距离
};bool cmp(node a, node b)
{return a.z b.z; // 根据z值排序
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 根据题目描述HKE的攀爬路线是根据高度从低到高一个一个点的爬即根据z值从小到大依次往上爬// 那么我们只需将读入的点的数据依据z值进行排序再计算总距离即可int n;cin n;vectornode point(n);for (int i 0; i n; i){cin point[i].x point[i].y point[i].z;}sort(point.begin(), point.end(), cmp); // 我们使用STL的快排函数并自己定义比较函数double ans 0; // 存储总距离即答案for (int i 0; i n - 1; i) // 由于需要计算的距离有n-1个所以循环n-1次{// 第一个点的坐标double x1 point[i].x;double y1 point[i].y;double z1 point[i].z;// 第二个点的坐标double x2 point[i 1].x;double y2 point[i 1].y;double z2 point[i 1].z;// 计算两点距离double distance sqrt(pow(x1 - x2, 2) pow(y1 - y2, 2) pow(z1 - z2, 2));// 总距离加上该结果ans distance;}cout fixed setprecision(3) ans \n; // 记得保留三位小数return 0;
}
