曼哈顿距离与切比雪夫距离
title: 曼哈顿距离与切比雪夫距离
categories:
- ICPC
tags:
- null
abbrlink: b4c59b70
date: 2023-03-04 00:00:00
曼哈顿距离与切比雪夫距离
距离 - 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)$
曼哈顿距离与切比雪夫距离的相互转化
结论：
- 曼哈顿坐标系是通过切比雪夫坐标系旋转 $\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:假如没学过这个套路，应该如何思考？
- 注：然后会发现以上两种思路的代码实现是一样的。
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;
}
针对上题的总结：
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个属性。现在你要最大化下面这个式子。
也就是需要得分相加大，属性相差绝对值大，且两者和加起来大。注意满足的优先级。
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)