title: 曼哈顿距离与切比雪夫距离
categories:

  • ICPC
    tags:
  • null
    abbrlink: b4c59b70
    date: 2023-03-04 00:00:00

曼哈顿距离与切比雪夫距离

距离 - OI Wiki (oi-wiki.org)已经说的比较清晰，提取要点和结论便于复习使用。

曼哈顿距离：d(A,B)=∣x1−x2∣+∣y1−y2∣d \left(\right. A , B \left.\right) = \left|\right. x_{1} - x_{2} \left|\right. + \left|\right. y_{1} - y_{2} \left|\right.

切比雪夫距离：d(A,B)=max(∣x1−x2∣,∣y1−y2∣)d \left(\right. A , B \left.\right) = max \left(\right. \left|\right. x_{1} - x_{2} \left|\right. , \left|\right. y_{1} - y_{2} \left|\right. \left.\right)

曼哈顿距离与切比雪夫距离的相互转化

image-20240428170225637

结论：

  • 曼哈顿坐标系是通过切比雪夫坐标系旋转 (45)∘\left(45\right)^{\circ} 后，再缩小到原来的一半得到的。
  • 将一个点 (𝑥,𝑦) 的坐标变为 (𝑥+𝑦,𝑥−𝑦) 后，原坐标系中的曼哈顿距离等于新坐标系中的切比雪夫距离
  • 将一个点 (𝑥,𝑦) 的坐标变为 (x+y2,x−y2)\left(\right. \frac{x + y}{2} , \frac{x - y}{2} \left.\right) 后，原坐标系中的切比雪夫距离等于新坐标系中的曼哈顿距离

用处

  • 切比雪夫距离在计算的时候需要取max，往往不是很好优化，对于一个点，计算其他点到该的距离的复杂度为O(n)

  • 而曼哈顿距离只有求和以及取绝对值两种运算，我们把坐标排序后可以去掉绝对值的影响，进而用前缀和优化，可以把复杂度降为O(1)

  • 注意到切比雪夫转曼哈顿中除法如果向下取整可能会使答案不正确，所以考虑先不除以2，最后求完答案再除以2也是一样的。

[曼哈顿距离与切比雪夫距离的互相转化 && 点对距离之和初步 - louis_11 - 博客园 (cnblogs.com)](https://www.cnblogs.com/qqq1112/p/15121123.html#:~:text=曼哈顿距离： %24Manhattandis (i%2C%24 %24j)%24 %24%3D%24 %24|x_i%24 %24-%24 %24x_j|%24,%24y1)

例题

1.https://leetcode.cn/problems/minimize-manhattan-distances/description/

题意：在二维平面上，给你若干个点。请你恰好移除一个点，返回移除后剩余任意两点之间的 最大曼哈顿 距离可能的 最小 值。

Solution:直接存入的转化为的切比雪夫距离,然后枚举删除的点，使用multiset维护x和y的所有取值，最大值就是当前剩余点中的max(最大x-最小x，最大y-最小y)

class Solution {
    #define pii pair<int,int>
   // #define int long long
    int cal(int x1,int x2,int y1,int y2){
       // cout<<x1<<" "<<x2<<" "<<y1<<" "<<y2<<endl;
        return max(abs(x1-x2),abs(y1-y2));
        
    }
public:
    int minimumDistance(vector<vector<int>>& points) {
        multiset<int>mstx;
         multiset<int>msty;
        multiset<pii>po;
        for(auto x:points){
        int y=x[0],w=x[1];
            int tx=y+w;int ty=y-w;
            po.insert({tx,ty});
            mstx.insert(tx);msty.insert(ty);
        }
        int ans=1e9;
       
        for(auto x:po){
                auto [y,w]=x;
                mstx.erase(mstx.find(y));
                msty.erase(msty.find(w));
                ans=min(ans,cal(*mstx.begin(),*mstx.rbegin(),*msty.begin(),*msty.rbegin()));
                mstx.insert(y);msty.insert(w);
              
        }
        return ans;
    }
};

曼哈顿转切比雪夫https://www.luogu.com.cn/problem/P5098

题意：给定若干二维平面的点，求其中两点的最大曼哈顿距离

Sol1:考虑存入变换后的坐标，然后直接最值相减取max即可

void solve(){
	cin>>n;
	vector<int>v1,v2;
	for(int i=0;i<n;i++){int x,y;cin>>x>>y;v1.push_back(x+y);v2.push_back(x-y);}
	int res1=*max_element(alls(v1))-*min_element(alls(v1));
	int res2=*max_element(alls(v2))-*min_element(alls(v2));
	cout<<max(res1,res2)<<endl;
}

Sol2:假如没学过这个套路，应该如何思考？

image-20240506124639455

  • 注：然后会发现以上两种思路的代码实现是一样的。

P3964 [TJOI2013] 松鼠聚会https://www.luogu.com.cn/problem/P3964

题意：有N个二位平面上的点，定义每一个点到其八连通的点的距离为1。选一个点，使得剩下所有点到该点的距离之和最小，求出这个距离之和。

Sol：本题是切比雪夫转曼哈顿来处理。注意到题目中给出的距离是切比雪夫距离的定义，要求距离之和我们考虑转化为曼哈顿以后利用排序和前缀和来处理。坐标转换的时候涉及除法，我们最后直接对答案除，不在中间计算过程除，防止精度损失。

具体实现：题意即为求切比雪夫距离之和最小，暴力的做法是O(N2)O(N^2)的。考虑将切比雪夫距离转化为曼哈顿距离，我们将横纵坐标分开排序求前缀和，这样既可快速求出，以一个点为中心，其他点到这个点的曼哈顿距离之和。

  • 具体的做法是将两个坐标分开讨论，每次找到当前点在排序后数组的位置p。

  • 那么它前面的点坐标都小于当前点，累加的答案为p×x[i]−sumpp\times x[i]-sum_p。

  • 后面的点的坐标都大于当前点，反过来累加答案，为(sumn−sump)−(n−p)×x[i](sum_n-sum_p)-(n-p)\times x[i]

对所有的点都枚举一遍，取最小值即可，复杂度O(NlogN)O(NlogN)

//切比雪夫转曼哈顿
void solve(){
	cin>>n;
	vector<pii>v1(n+1),v2(n+1);
	for(int i=1;i<=n;i++){
		int x,y;cin>>x>>y;
		v1[i]={x+y,i};
		v2[i]={x-y,i};
	}
	sort(alls(v1));
	sort(alls(v2));
	vector<int>ans(n+1);
	vector<int>pre1(n+1);
	vector<int>pre2(n+1);
	int s1=0,s2=0;
	for(int i=1;i<=n;i++){
		pre1[i]=pre1[i-1]+v1[i].fs;
		s1+=v1[i].fs;
		pre2[i]=pre2[i-1]+v2[i].fs;
		s2+=v2[i].fs;
	}
	for(int i=1;i<=n;i++){
		int c1=v1[i].fs*(i-1)-pre1[i-1]+(s1-pre1[i])-(n-i)*v1[i].fs;
		c1=abs(c1);
		int c2=v2[i].fs*(i-1)-pre2[i-1]+(s2-pre2[i])-(n-i)*v2[i].fs;
		c2=abs(c2);
		ans[v1[i].sec]+=c1;ans[v2[i].sec]+=c2;
		
	}
	int res=*min_element(alls(ans));
	cout<<res/2<<endl;
}

针对上题的总结：

image-20240506133548142

img

https://atcoder.jp/contests/abc351/tasks/abc351_e ABC351E

前置知识：坐标轴旋转后点的变换公式2.3.

逆变换公式建2.4

问题陈述

在坐标平面上有 NN 个点 P1,P2,…,PNP_1, P_2, \ldots, P_N ，其中点 PiP_i 的坐标为 (Xi,Yi)(X_i, Y_i) 。
两点 AA 与 BB 之间的距离 dist(A,B)\text{dist}(A, B) 定义如下：

一只兔子最初位于点 AA 。
位置为 (x,y)(x, y) 的兔子可以跳跃到 (x+1,y+1)(x+1, y+1) 、 (x+1,y−1)(x+1, y-1) 、 (x−1,y+1)(x-1, y+1) 或 (x−1,y−1)(x-1, y-1) 。
dist(A,B)\text{dist}(A, B) 被定义为从 AA 点跳到 BB 点所需的最少跳跃次数。
如果经过任意次数的跳跃都无法从点 AA 到达点 BB ，则设为 dist(A,B)=0\text{dist}(A, B) = 0 。

计算总和 ∑i=1N−1∑j=i+1Ndist(Pi,Pj)\displaystyle\sum_{i=1}^{N-1}\displaystyle\sum_{j=i+1}^N \text{dist}(P_i, P_j) 。

Sol：考虑这样的移动方式难以计算，我们使用旋转变换

将平面相对于原点旋转 4545 度，并缩放 2\sqrt{2} 倍。然后，原先位于 (X,Y)(X,Y) 的点移动到 (X+Y,X−Y)(X+Y,X-Y) 。
设 (xi,yi)(x_i,y_i) 为经过此变换后各点 PiP_i 的坐标。那么， xi=Xi+Yix_i=X_i+Y_i 和 yi=Xi−Yiy_i=X_i-Y_i 。

  • 接下来，我们来看看 dist(A,B)\text{dist}(A,B) 的定义是如何变化的。
    在最初的定义中，兔子可以从 (X,Y)(X,Y) 跳转到 (X+1,Y+1)(X+1,Y+1) 、 (X+1,Y−1)(X+1,Y-1) 、 (X−1,Y+1)(X-1,Y+1) 和 (X−1,Y−1)(X-1,Y-1) ；
    因此，经过变换后，它可以从 (X+Y,X−Y)(X+Y,X-Y) 跳到 (X+Y+2,X−Y)(X+Y+2,X-Y) 、 (X+Y,X−Y+2)(X+Y,X-Y+2) 、 (X+Y,X−Y−2)(X+Y,X-Y-2) 和 (X+Y−2,X−Y)(X+Y-2,X-Y) 。

  • 替换 x=X+Yx=X+Y 和 y=X−Yy=X-Y 后，可以从 (x,y)(x,y) 跳转到 (x+2,y)(x+2,y) 、 (x,y+2)(x,y+2) 、 (x,y−2)(x,y-2) 和 (x−2,y)(x-2,y) 。
    从 AA 到达 BB 所需的最少跳转次数就是 dist(A,B)\text{dist}(A,B) 的定义（如果无法到达，则为 00 ）。

下面，我们考虑变换后的问题。
也就是说，我们设 Pi=(xi,yi)P_i=(x_i,y_i) ，定义 dist(A,B)\text{dist}(A,B) ，并考虑和 ∑i=1N−1∑j=i+1Ndist(Pi,Pj)\displaystyle\sum_{i=1}^{N-1}\displaystyle\sum_{j=i+1}^N \text{dist}(P_i,P_j) 与上述 dist(A,B)\text{dist}(A,B) 的定义。
显然，这样得到的答案与原答案相同。

我们进一步将 dist(A,B)\text{dist}(A,B) 视为 A=(x1,y1)A=(x_1,y_1) ， B=(x2,y2)B=(x_2,y_2) 。如果是 x1≢x2(mod2)x_1\not\equiv x_2 \pmod{2} 或 y1≢y2(mod2)y_1\not\equiv y_2 \pmod{2} ，兔子就无法从 AA 到达 BB ，因此是 dist(A,B)=0\text{dist}(A,B)=0 。否则，计算结果正好是曼哈顿距离的一半，即 12(∣x1−x2∣+∣y1−y2∣)\frac{1}{2}(\lvert x_1-x_2\rvert+\lvert y_1-y_2\rvert) 。

注意到所有 ii 的 xi=yi+2Yi≡yi(mod2)x_i=y_i+2Y_i\equiv y_i \pmod{2} ， NN 个点可以分为两组： xix_i 和 yiy_i 都是偶数，或者 xix_i 和 yiy_i 都是奇数。属于不同组的两个点 AA 和 BB 为 dist(A,B)=0\text{dist}(A,B)=0 ；属于同一组的两个不同点为 dist(A,B)=12(∣x1−x2∣+∣y1−y2∣)\text{dist}(A,B)=\frac{1}{2}(\lvert x_1-x_2\rvert+\lvert y_1-y_2\rvert) 。

不失一般性，我们考虑计算变换后的x都是偶数的情况，对于这样的点我们直接先对x排序，利用前缀和计算答案，这个计算方式在前面题目已经涉及。再给出一种方式，看贡献次数。假设下标从0开始，排序后后的元素xjx_j对前面的贡献是j*a[i],对后面的贡献是−a[i]×(sz−j−1)-a[i]\times(sz-j-1),两项合并加起来就是答案。

将同样的讨论应用于 yy 坐标，可以求出 ∑i=1∣E∣−1∑j=i+1∣E∣dist(PEi,PEj)\displaystyle\sum_{i=1}^{\lvert E\rvert-1}\displaystyle\sum_{j=i+1}^{\lvert E\rvert} \text{dist}(P_{E_i},P_{E_j}) ；将同样的讨论应用于奇数 xix_i 和 yiy_i 的组，可以求出最终的和。

对两组的坐标 xx 和 yy 进行排序需要花费 O(Nlog⁡N)O(N\log N) 时间，剩下的计算花费可以在 O(N)O(N) 时间内完成，所以这个问题总共可以在 O(Nlog⁡N)O(N\log N) 时间内解决，速度足够快。因此，问题已经解决。

vector<int>a[4];
void solve(){
	cin>>n;
	for(int i=0;i<n;i++){
		int x,y;cin>>x>>y;
		if((x+y)%2){
			a[0].push_back(x+y);
			a[1].push_back(x-y);
		}
		else {
			a[2].push_back(x+y);
			a[3].push_back(x-y);
		}
	}
	for(int i=0;i<4;i++)sort(alls(a[i]));
	int ans=0;
	for(int i=0;i<4;i++){
		int sz=a[i].size();
		for(int j=0;j<sz;j++){
			ans+=a[i][j]*(2*j+1-sz);
		}
	}
	cout<<ans/2<<endl;
}

思路总结：坐标旋转转化为常规曼哈顿，注意到移动距离变成2倍，造成的影响有最后答案要除2以及横纵坐标之间必须mod2相同才可达。值得注意的是在这样变换下，一个点的横坐标和纵坐标一定是mod2同余的。

k维空间有n个点，求 k维曼哈顿距离最大值。首先从某ioi题目中得知：当k维曼哈顿转换成切比雪夫，变化的复杂度较高且不是线性。我们只能另寻他法。

https://vjudge.net/problem/POJ-2926

题意：给定若干五维点，求其中的两点之间的最大曼哈顿距离值

Sol:我们仔细对于二维的情况刨析，也就是前面的题目说没有套路的时候的思考方式，发现我们可以枚举正负号。比较关键的一点是减数与被减数在我们钦定符号后一定可以同构。

db a[N][6];
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
	for(int j=0;j<5;j++){
		cin>>a[i][j];
	}
}

db ans=0;
for(int i=0;i<32;i++){
	//初始化需要设置无穷，可能全是负的状态
	db mx=-1e13,mn=1e13;
	vector<db>sg(5);
	for(int j=4;j>=0;j--){
		if((i>>j)&1)sg[j]=1.0;
		else sg[j]=-1.0;
	}
	// cerr<<i<<endl;
	// for(auto x:sg)cerr<<x<<" ";
	// cerr<<endl;
	for(int j=1;j<=n;j++){
		db tmp=0;
		for(int k=0;k<5;k++){
			tmp+=sg[k]*a[j][k];
		}
		mx=max(mx,tmp);
		mn=min(mn,tmp);
	}
	ans=max(ans,mx-mn);
}
baoliu(ans,2);
}

k维曼哈顿距离的应用https://vjudge.net/problem/HDU-6435#author=GPT_zh

题意：n个主武器，m个副武器，每个武器有一个得分，和k个属性。现在你要最大化下面这个式子。img

也就是需要得分相加大，属性相差绝对值大，且两者和加起来大。注意满足的优先级。

int a[N][10];
int b[N][10];
void solve(){
	    int k;
       cin>>n>>m>>k;
       for(int i=1;i<=n;i++){
       	int x;cin>>x;a[i][0]=x;
       	for(int j=2;j<k+2;j++)cin>>a[i][j];
       }
       for(int i=1;i<=m;i++){
       	int x;cin>>x;b[i][1]=x;
       	for(int j=2;j<k+2;j++)cin>>b[i][j];
       }
      ll ans=0;
     
       for(int s=0;s<(1<<(k+2));s++){
     ll tmp=0;
      ll mx1=-1e18,mn1=1e18;
      ll mx2=-1e18,mn2=1e18;
      for(int i=1;i<=n;i++){
      tmp=0;
      	for(int j=0;j<k+2;j++){
      		if((s>>j)&1)tmp+=a[i][j];
      		else tmp-=a[i][j];
      	}
      	 mx1=max(tmp,mx1);mn1=min(tmp,mn1);
      }
      for(int i=1;i<=m;i++){
      	tmp=0;
      	for(int j=0;j<k+2;j++){
      		if((s>>j)&1)tmp+=b[i][j];
      		else tmp-=b[i][j];
      	}
      	mx2=max(tmp,mx2);mn2=min(tmp,mn2);
      }
      ans=max({ans,mx2-mn1,mx1-mn2});
      
       }
       cout<<ans<<endl;
}

未完待续…

https://www.luogu.com/article/hxr7p6po

https://www.luogu.com.cn/problem/P4648

曼哈顿距离最小生成树 - GGBeng - 博客园 (cnblogs.com)

论一类平面点对曼哈顿距离问题 - 百度文库 (baidu.com)

浅谈信息学竞赛中的“0”和“1” - 道客巴巴 (doc88.com)