欧几里得距离、曼哈顿距离和切比雪夫距离
发布时间
阅读量：
阅读量
定义：
1. 欧几里得距离
公式（n维空间下）
二维：dis=sqrt( (x1-x2)^2 + (y1-y2)^2 )
三维：dis=sqrt( (x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2 )
2.曼哈顿距离：两个点在标准坐标系上的绝对轴距总和
3.切比雪夫距离：各坐标数值差的最大值
曼哈顿距离与切比雪夫距离的关系：
两者的定义看上去好像没有关系，但实际上，这两种距离可以相互转化！
我们考虑最简单的情况，在一个二维坐标系中，设原点为(0,0)
如果用曼哈顿距离表示，则与原点距离为11的点会构成一个边长为1的正方形
如果用切比雪夫距离表示，则与原点距离为1的点会构成一个边长为2的正方形
仔细对比这两个图形，你会发现什么？ 额(⊙o⊙)…
第二个图像是由第一个图像放大两倍后旋转45°得到的！没错，就是这样！
然后根据向量矩阵坐标三角换元什么乱七八糟的可以得到
第一个图中的点(x,y)对应第二个图中的点( (x+y)/2,(x-y)/2) 非常有用！！！
这样我们就可以将其进行互相转换了！
例题：
1、bzoj 3170: [Tjoi2013]松鼠聚会 ->题解戳这里（博主真帅），当然还是我的博客啦！
全部评论 (0)
还没有任何评论哟~