题目大意

在一个2D平面上有N个点,定义两个点之间的距离为曼哈顿距离,求最大距离的值.

数据范围

(1 leq n leq 2e5)

(1 leq x_i,y_i leq 1e9)

思路

由于(n)导致不能(n^2)肯定有什么压复杂度的办法,一个比较浅显的思路就是先对绝对值下手:先对(x)进行排序,对于当前考虑的(x_i)只考虑比他(x)更小的点(j)这样可以让一个绝对值(|x_i - x_j|)被拿掉,但是很明显(y_i)这部分还是没法做,因为两个信息并不是独立的,每个(x_j)拿出来做绝对值的运算虽然很好做,并且能直接地确定他们俩的贡献,但是没办法在此基础上快速找出最大的(y)能提供的贡献,因为信息不独立所以不能分开计算.

这里另外一种思路就是对表达式本身下手:

(|x_i - x_j| + |y_i - y_j|)

=(max(x_i - x_j,x_j - x_i) + max(y_i - y_j,y_j - y_i))

=(max((x_i - x_j)+(y_i - y_j),(x_i - x_j)+(y_j - y_i),(x_j - x_i) +(y_i - y_j),(x_j - x_i)+(y_j - y_i)))

合并一下相同的项,看一下是否有规律

=(max((x_i +y_i - (x_j +y_j),x_i - y_i - (x_j - y_j),-(x_i - y_i)+(x_j - y_j),-(x_i + y_i)+x_j +y_j)))

这里我们可以发现第一个和第三个表达式互为相反数,第二个和第四个同理,可以转回绝对值表达式

=(max(|x_i + y_i - (x_j + y_j)|,|x_i - y_i - (x_j - y_j)|))

令(z_i = x_i + y_i,w_i = x_i - y_i)

=(max(|z_i - z_j|,|w_i - w_j|))

到这里就可以直接把原来的问题进行转换了:

(max_{1 leq i,jleq n}(max(|x_i - x_j| + |y_i - y_j|)))

=(max{max_{1 leq i,j leq n}(|z_i - z_j|,|w_i - w_j|)})

=(max{(max_{1 leq i leq n} z_i - min_{1 leq i leq n} z_i),(max_{1 leq i leq n} w_i - min_{1 leq i leq n} w_i)})

剩下的预处理出(z_i,w_i)的最大最小值就可以算出答案了,整体线性.

关于这种方法,本身转换这一步可以看做是把坐标旋转45°之后得到的,这样转换之后可以做的一个原因就是成功地把绝对值分离(把(i)和(j)分离出去)了.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define x first
#define y second

const int N = 2e5+7;
pii p[N];
int z[N],w[N];
int main()
{
	int n;scanf("%d",&n);
    for(int i = 1;i <= n;++i)	scanf("%d%d",&p[i].x,&p[i].y);
    for(int i = 1;i <= n;++i)	z[i] = p[i].x + p[i].y,w[i] = p[i].x - p[i].y;
    
    int maxz = z[1],minz = z[1],maxw = w[1],minw = w[1];
    for(int i = 1;i <= n;++i)
    {
    	maxz = max(maxz,z[i]);
    	minz = min(minz,z[i]);
    	
    	maxw = max(maxw,w[i]);
    	minw = min(minw,w[i]);
    }
    printf("%d",max(maxz - minz,maxw - minw));
    return 0;
}