题解 | #最大 FST 距离#

注意到式子 很像曼哈顿距离的公式，故考虑转化。

考虑二维平面内的 个点 ，那么答案就是这 个点中所有点对曼哈顿距离的最大值。

我们可以将曼哈顿距离转化为切比雪夫距离，也就是 这些点中的切比雪夫距离的最大值，证明过程 见此处。

这个切比雪夫距离很好求，排序一下即可。

Code:

const int maxn=1e5+5;
int n;
ll x[maxn],y[maxn];
int main() {
    cin>>n;
    for(int i=1;i<=n;i++) {
        ll a; cin>>a;
        x[i]=1ll*i*i+a*a;
        y[i]=1ll*i*i-a*a;
    }
    sort(x+1,x+1+n);
    sort(y+1,y+1+n);
    cout<<max(abs(x[1]-x[n]),abs(y[1]-y[n]));
    return 0;
}