定义:
二维下点坐标 ( 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
来源: http://www.bubuko.com/infodetail-3128404.html