以HDU 4311和HDU 4312为例

如图所示，Manhattan距离是指 1-2,2-4,3-4,4-1之间距离都为1，而对角线路线不可达状态下的两点距离

Chebyshev距离是指除曼哈顿距离外，对角线路线可达且距离为1的情况下（即 1-4，2-3之间距离为1），两点之间的距离

平面上两点间的 Manhattan 距离为 |x1-x2| + |y1-y2|，平面上两点间的 Chebyshev距离为 max(|x1-x2|, |y1-y2|)。

两种距离之间的特性为：设在常规坐标中(x1,y1),(x2,y2)两点之间的Chebyshev距离为的d1,那么在将此坐标系顺时针旋转45度，并将新坐标系所有点两轴坐标分别乘以√2后，得到新的两点坐标(x1′,y1′),(x2′,y2′),该两点之间曼哈顿距离为d2,那么d2=2×d1.

例(0,0),(1,1)两点Chebyshev距离为1,坐标系旋转后，两点坐标为(0,0),(0,√2),再分别乘以√2后，得到新的坐标(0,0),(0,2),该两点之间曼哈顿距离为2,则2=1×2;

另可证：x1′=(x1-y1) , y1′=(x1+y1)

即：若要求两点之间的Chebyshev距离，可以在将所求点都变为(x1-y1,x1+y1)之后求其曼哈顿距离再除以2

和 4311 的区别在于一个转换

原来的两点 (x1,y1) (x2,y2) 转换为 (x1-y1,x1+y1) (x2-y2,x2+y2)

最后记得除以2

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
typedef long long ll;
using namespace std;
struct point
{
    ll px;
    ll py;
    ll dx;
    ll dy;
}p[100001];
int cmpx(point x,point y)
{
    return (x.px<y.px);
}
int cmpy(point x,point y)
{
    return (x.py<y.py);
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        memset(p,0,sizeof(p));
        int n;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            cin>>p[i].px>>p[i].py;
        }
        sort(p,p+n,cmpx);
        //int sumx;
        for(int i=1;i<n;i++)
        {
            p[0].dx+=p[i].px-p[0].px;
        }
        for(int i=1;i<n;i++)
        {
            p[i].dx=p[i-1].dx+(i+i-n)*(p[i].px-p[i-1].px);
        }
        sort(p,p+n,cmpy);
        for(int i=1;i<n;i++)
        {
            p[0].dy+=p[i].py-p[0].py;
        }
        for(int i=1;i<n;i++)
        {
            p[i].dy=p[i-1].dy+(i+i-n)*(p[i].py-p[i-1].py);
        }
        ll minv=p[0].dx+p[0].dy;
        for(int i=0;i<n;i++)
        {
            if(p[i].dx+p[i].dy<minv)
            {
                minv=p[i].dx+p[i].dy;
            }
        }
        cout<<minv<<endl;
 
    }
    return 0;
}

4312

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
typedef long long ll;
using namespace std;
struct point
{
    ll px;
    ll py;
    ll dx;
    ll dy;
}p[100001];
int cmpx(point x,point y)
{
    return (x.px<y.px);
}
int cmpy(point x,point y)
{
    return (x.py<y.py);
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        memset(p,0,sizeof(p));
        int n;
        cin>>n;
        ll tx,ty;
        for(int i=0;i<n;i++)
        {
            cin>>tx>>ty;
            p[i].px=tx-ty;
            p[i].py=tx+ty;
        }
        sort(p,p+n,cmpx);
        //int sumx;
        for(int i=1;i<n;i++)
        {
            p[0].dx+=p[i].px-p[0].px;
        }
        for(int i=1;i<n;i++)
        {
            p[i].dx=p[i-1].dx+(i+i-n)*(p[i].px-p[i-1].px);
        }
        sort(p,p+n,cmpy);
        for(int i=1;i<n;i++)
        {
            p[0].dy+=p[i].py-p[0].py;
        }
        for(int i=1;i<n;i++)
        {
            p[i].dy=p[i-1].dy+(i+i-n)*(p[i].py-p[i-1].py);
        }
        ll minv=p[0].dx+p[0].dy;
        for(int i=0;i<n;i++)
        {
            if(p[i].dx+p[i].dy<minv)
            {
                minv=p[i].dx+p[i].dy;
            }
        }
        cout<<minv/2<<endl;
 
    }
    return 0;
}