题解 P5098 【[USACO2004OPEN]Cave Cows 3 洞穴里的牛之三】
米奇奇米
·
·
题解
这道题目难度不是很大的，主要就是分类讨论。
1.1题目意思
题目意思很简单，就是让你找出一对点对使得两点之间曼哈顿距离最大。
2.1暴力大法
这道题目(N<=5e4)显然O(n^2)暴力不能过。
3.1正解
这道题目难就难在分类讨论：
我们已经知道原式为：|xi-xj|+|yi-yj|
我们先来考虑几种情况：
$B.$当$xi<xj$以及$yi>yj$的时候，此时原式转换为：$-(xi-yi)+(xj-yj)$此时我们像情况$A$一样，让$xi-yi$尽量小，$xj-yj$尽量大。
最后只要比较$A,B$这两种情况谁大谁小就可以了：$ans=max(a-b,c-d)$，这样我们就将复杂度缩小到$O(n)$。
### $4.1$代码实现
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e4+5;
struct xjh {
int x,y;
} num[maxn];
int n,a,b=1e12,c,d=1e12;
inline int read() {
int sum=0,ff=1; char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-') ff=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
sum=sum*10+ch-48;
ch=getchar();
}
return sum*ff;
}
int main() {
n=read();
for ( int i=1;i<=n;i++ ) {
num[i].x=read(),num[i].y=read();
a=max(a,num[i].x+num[i].y);
b=min(b,num[i].x+num[i].y);
c=max(c,num[i].x-num[i].y);
d=min(d,num[i].x-num[i].y);
}
printf("%d\n",max(a-b,c-d));
return 0;
}
```