正文前提示

题目传送门

主要思路

这道题，我们都可以维护一个最大值来求答案。

• 对于 $op=1$，我们要求最大的 $\sqrt{\left(x_i-x_j\right)^2+\left(y_i-y_j\right)^2}^2$，但是 double 的精度会有限，就算开 long double 也无法保证 AC。其实 $\sqrt{x}^2$ 还是 $x$，所以我们只要看最大的 $\left(x_i-x_j\right)^2+\left(y_i-y_j\right)^2$ 就 OK 了。数据范围在 $1000$ 级别，可以放心使用双重循环。
• 对于 $op=2$，我们要求最大的 $\left|x_i-x_j\right|+\left|y_i-y_j\right|$。但是 $n$ 的范围在 $10^6$，我们不得不使用单重循环。分析一下，我们可以把 $\left|x_i+y_i\right|$ 的最大值和最小值求出来，再把 $\left|x_i-y_i\right|$ 的最大值和最小值求出来，再求 $\left|x_i+y_i\right|$ 的最大值减最小值和 $\left|x_i-y_i\right|$ 的最大值减最小值哪个更大，大的那个就是答案。具体请见代码。这样就可以把复杂度缩减成 $\mathcal O\left(n\right)$。这里需要用到 abs（绝对值）函数，需调用 cmath 或 math.h 库。

AC 代码

#include<iostream>
#include<math.h>
using namespace std;
long long dian[1451478][2];
int main(){
    int n,op;
    long long maxn=-0x7f7f7f7f7f7f7f7f,minn=0x7f7f7f7f7f7f7f7f,
              maxx=-0x7f7f7f7f7f7f7f7f,minx=0x7f7f7f7f7f7f7f7f;
    cin>>n>>op;
    for(int i=1;i<=n;i++){
        cin>>dian[i][1]>>dian[i][2];
    }
    if(op==1){
        for(int i=1;i<n;i++){
            for(int j=i+1;j<=n;j++){
                
                //很容易出错，要小心！！！
                long long x=dian[i][1]-dian[j][1];
                long long y=dian[i][2]-dian[j][2];
                
                maxn=max(maxn,x*x+y*y);
            }
        }
        cout<<maxn;
    }else{
        for(int i=1;i<=n;i++){
            long long x=dian[i][1]+dian[i][2];
            long long y=dian[i][1]-dian[i][2];
            maxn=max(maxn,x);
            minn=min(minn,x);
            maxx=max(maxx,y);
            minx=min(minx,y);
        }
        cout<<max(maxn-minn,maxx-minx);
    }
    return 0;
}