切比雪夫距离和曼哈顿距离就是变成了八个方向只用一步

首先八个方向距离就变成了max(|x1-x2|,|y1-y2|)这样的一个最值式，似乎并没有什么卵用

学到了一个非常机智的转化： max(|x1-x2|,|y1-y2|)=(|x1-x2+y1-y2|+|x1-x2-y1+y2|)/2 。

这个公式需要从两条45°对角线仔细考虑

然后就和4312几乎一样了==

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 struct dian{ 6   long long x,y,id; 7 }a[100005],f[100005]; 8 int cmp1(dian n1,dian n2) 9 {10   return n1.y
        
       
      

题目链接：