自动搬运

查看原文

来自洛谷，原作者为

	Siyuan Dream OIer.

搬运于2025-08-24 22:07:07，当前版本为作者最后更新于2018-12-17 19:15:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$$\Large\texttt{My Blog}$$

题目链接：Luogu 5098

约翰的 $n$ 只奶牛在一个洞里探险，他们只能通过叫声交流。用坐标 $(x_i,y_i)$ 表示第 $i$ 只牛的位置，两只牛之间的曼哈顿距离决定了声音传播的时间，即第 $i$ 只牛和第 $j$ 只牛交流，需要的时间为 $|x_i-x_j|+|y_i-y_j|$。求出任意一对牛之间交流需要的时间的最大值。

Solution

由于 $i$ 和 $j$ 是无序的，我们强制 $x_i\ge x_j$，那么我们对 $y$ 进行分类讨论：

1. 如果 $y_i\ge y_j$，那么 $\texttt{原式}=x_i-x_j+y_i-y_j=(x_i+y_i)-(x_j+y_j)$。答案最大为 $\max_{x+y}-\min_{x+y}$。
2. 如果 $y_i<y_j$，那么 $\texttt{原式}=x_i-x_j-y_i+y_j=(x_i-y_i)-(x_j-y_j)$。答案最大为 $\max_{x-y}-\min_{x-y}$。

所以我们只需要维护 $x+y$ 和 $x-y$ 的最大值和最小值就行了。

时间复杂度：$O(n)$

Code

#include <cstdio>
#include <algorithm>

const int inf=1<<30;

int main() {
    int n,a=-inf,b=inf,c=-inf,d=inf;
    for(scanf("%d",&n);n--;) {
        int x,y;
        scanf("%d%d",&x,&y);
        a=std::max(a,x+y);
        b=std::min(b,x+y);
        c=std::max(c,x-y);
        d=std::min(d,x-y);
    }
    printf("%d\n",std::max(a-b,c-d));
    return 0;
}