n个点，求任意两点曼哈顿距离 的最大值

设点A(x1,y1),B(x2,y2);

则man(A,B)=|x1-x2|+|y1-y2|;

这种不好处理，我们把他变成相减的形式：

(a * x1 + b * y1) - (a * x2 - b * y2)

其中a，b取值为：1,-1.

为什么两个括号的a相同？ 显然：对|x1-x2|取掉绝对值后， x1,-x2 的符号同时改变，而我们要改成相减的形式，把-x2的负号消去，所以x1,x2的符合就相同了。

y1，y2同理。

得到上述式子后我们就可以这样做：

由于左右括号均只与某个点有关。所以我们把每个点的  2*2种符号情况存下来，然后用每种情况的最大值减去最小值 就是最大曼哈顿距离。

为什么？ 显然有： 某种情况下：x1-x2>=0,y1-y2>=0,此时man(A,B)最大。这种情况下，让最大值减去最小值，是这种情况下两个点的最大差值，即最大曼哈顿距离。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 2e5+7;

int x[M],y[M];
int p[4][M];
int main()
{
	ios::sync_with_stdio(false);
  	cin.tie(0);
  	int n;
  	cin>>n;
  	for(int i=1;i<=n;i++)
  	{
  		cin>>x[i]>>y[i];
  		p[0][i]=x[i]+y[i];
  		p[1][i]=-x[i]+y[i];
  		p[2][i]=x[i]-y[i];
  		p[3][i]=-x[i]-y[i];
	}
	for(int i=0;i<4;i++)sort(p[i]+1,p[i]+1+n);
	int mx=0;
	for(int i=0;i<4;i++)
	{
		mx=max(mx,p[i][n]-p[i][1]);
		//cout<<i<<"  "<<p[i][n]<<"  "<<p[i][1]<<endl;
	}
	cout<<mx<<endl;
	return 0;
}

值得一提的是：多维曼哈顿距离最大值同样可以用这种方法：

复杂度为：2^k * n * log n    ,k是维度。

本文地址：https://blog.csdn.net/bjfu170203101/article/details/108567045