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

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

曼哈顿距离:$d \left(\right. A , B \left.\right) = \left|\right. x_{1} - x_{2} \left|\right. + \left|\right. y_{1} - y_{2} \left|\right.$

切比雪夫距离:$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

结论:

  • 曼哈顿坐标系是通过切比雪夫坐标系旋转 $\left(45\right)^{\circ}$ 后,再缩小到原来的一半得到的。
  • 将一个点 (𝑥,𝑦) 的坐标变为 (𝑥+𝑦,𝑥−𝑦) 后,原坐标系中的曼哈顿距离等于新坐标系中的切比雪夫距离
  • 将一个点 (𝑥,𝑦) 的坐标变为 $\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(N^2)$的。考虑将切比雪夫距离转化为曼哈顿距离,我们将横纵坐标分开排序求前缀和,这样既可快速求出,以一个点为中心,其他点到这个点的曼哈顿距离之和。

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

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

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

对所有的点都枚举一遍,取最小值即可,复杂度$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

问题陈述

在坐标平面上有 $N$ 个点 $P_1, P_2, \ldots, P_N$ ,其中点 $P_i$ 的坐标为 $(X_i, Y_i)$ 。
两点 $A$ 与 $B$ 之间的距离 $\text{dist}(A, B)$ 定义如下:

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

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

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

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

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

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

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

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

注意到所有 $i$ 的 $x_i=y_i+2Y_i\equiv y_i \pmod{2}$ , $N$ 个点可以分为两组: $x_i$ 和 $y_i$ 都是偶数,或者 $x_i$ 和 $y_i$ 都是奇数。属于不同组的两个点 $A$ 和 $B$ 为 $\text{dist}(A,B)=0$ ;属于同一组的两个不同点为 $\text{dist}(A,B)=\frac{1}{2}(\lvert x_1-x_2\rvert+\lvert y_1-y_2\rvert)$ 。

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

将同样的讨论应用于 $y$ 坐标,可以求出 $\displaystyle\sum_{i=1}^{\lvert E\rvert-1}\displaystyle\sum_{j=i+1}^{\lvert E\rvert} \text{dist}(P_{E_i},P_{E_j})$ ;将同样的讨论应用于奇数 $x_i$ 和 $y_i$ 的组,可以求出最终的和。

对两组的坐标 $x$ 和 $y$ 进行排序需要花费 $O(N\log N)$ 时间,剩下的计算花费可以在 $O(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)