题解 | #最大 FST 距离#

emm....

将绝对值打开，只有四种情况：

$i^{2} - j^{2} + A_{i}^{2} - B_{j}^{2} = (i^{2} + A_{i}^{2}) - (j^{2} + B_{j}^{2})$

$i^{2} - j^{2} + B_{j}^{2} - A_{i}^{2} = (i^{2} - A_{i}^{2}) - (j^{2} - B_{j}^{2})$

$j^{2} - i^{2} + A_{i}^{2} - B_{j}^{2} = (j^{2} - B_{j}^{2}) - (i^{2} - A_{i}^{2})$

$j^{2} - i^{2} + B_{j}^{2} - A_{i}^{2} = (j^{2} + B_{j}^{2}) - (i^{2} + A_{i}^{2})$

所以就只需要对 $i^{2} + A_{i}^{2}$ 和 $i^{2} - A_{i}^{2}$ 排序即可

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


signed main(){
    HelloWorld;
    
    int n; cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for(int i = 1; i <= n; i ++){
        int x; cin >> x;
        a.push_back(i * i + x * x);
        b.push_back(i * i - x * x);
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    cout << max(a[n - 1] - a[0], b[n - 1] - b[0]) << endl;
    return 0;
}