题解 [USACO2004OPEN]洞穴里的牛之三

这道题目难度不是很大的，主要就是分类讨论。

题目意思

题目意思很简单，就是让你找出一对点对使得两点之间曼哈顿距离最大。

暴力大法

这道题目显然暴力不能过。

正解

这道题目难就难在分类讨论：

我们已经知道原式为：

我们先来考虑几种情况：

当以及的时候，此时原式将会转换为：。然后移项可得：，要让这个柿子的结果尽量大，我们就要让大，尽量小，这个很好理解：更大的减去更小的才能更大。

当以及的时候，此时原式转换为：此时我们像情况一样，让尽量小，尽量大。

最后只要比较这两种情况谁大谁小就可以了：，这样我们就将复杂度缩小到。

代码实现

#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;
}