题目链接:https://ac.nowcoder.com/acm/contest/877/J
时间限制：C/C++ 3秒，其他语言6秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

输入描述

输出描述

输入

2
2
4 3
4
5 4 -9 2

输出

10
84

解题思路

题意:求最大FST距离，即.
思路:我们可以令i>j,则上式有两种情况:
=i^2-j^2+Ai^2-Aj^2=i^2+Ai^2-(j^2-Aj^2);
或=i^2-j^2-Ai^2+Aj^2=i^2-Ai^2-(j^2-Aj^2);
故我们只需要分别求出i^2+Ai^2与i^2-Ai^2的最大最小值，然后求出最大最小值差的最大值。

#include <bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
int main() {
    int t, n;
    long long A, a, b, c, d, x, y;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        a = b = -INF, c = d = INF;
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &A);
            x = 1ll * i * i, y = A * A;
            a = max(a, x + y), b = max(b, x - y);
            c = min(c, x + y), d = min(d, x - y);
        }
        printf("%lld\n", max(a - c, b - d));
    }
    return 0;
}