定义两点(x1,y1),(x2,y2)的曼哈顿距离 定义两点(x1,y1),(x2,y2)的切比雪夫距离
切比雪夫与曼哈顿距离可以互相转化。 一个点曼哈顿距离中的点,用切比雪夫距离计算时用。 一个点切比雪夫距离中的点,用曼哈顿距离计算时用。
这有什么用呢? 在坐标系中画出来,可以发现距离(0,0)曼哈顿距离为1的点呈一个菱形(其实是正方形旋转135°(45°)),切比雪夫距离为1的呈正方形。 曼哈顿转切比雪夫:一般来说一个正方形状更便于用各类数据结构来维护。(例:洛谷4648 [IOI2007] pairs 动物对数 ) 切比雪夫转曼哈顿:一般是便于统计距离和。(例:3964 [TJOI2013]松鼠聚会)