曼哈顿距离，欧几里得距离学习笔记

1. 定义：

二维下点坐标 ( x , y )

空间里有两个点（ xi , yi )   ( xj , yj )

他们横坐标距离为 dx = | xi - xj | ，纵坐标距离为 dy = | yi - yj |

他们的切比雪夫距离是横坐标距离和纵坐标距离中值大的那一个 : max(dx,dy)

曼哈顿距离是横坐标距离与纵坐标距离的和 : dx+dy

　　2.  互相转换：

　　　　曼哈顿->切比雪夫：（ x , y ) -> ( (x+y/2) , (x-y/2) )

　　　　这里用换完后的坐标计算曼哈顿，算出来的是原坐标的切比雪夫距离，下面同理。

　　　　切比雪夫->曼哈顿： （ x , y ) -> (    x+y   ,   x-y     )

　  3.     题目：

              bzoj3170: [Tjoi2013]松鼠聚会

　　　　这是切比雪夫->曼哈顿，坑点在数据有点大，注意要先减后加，不然爆long long ，然后Inf要开到1e20

曼哈顿距离，欧几里得距离学习笔记

原文：https://www.cnblogs.com/jiecaoer/p/11215781.html