题解 | 最大 FST 距离

#include <algorithm>
#include <iostream>
#include<cmath>
using namespace std;
using ll=long long;

struct p{
    ll id_add_A;
    ll id_sub_A;
};

bool cmp1(p a1,p a2){
    return a1.id_add_A>a2.id_add_A;
}

bool cmp2(p a1,p a2){
    return a1.id_sub_A>a2.id_sub_A;
}





int main() {
    int n;cin>>n;
    p a[n+1];
    for(ll i=1;i<=n;++i){
        ll b;cin>>b;
        a[i].id_add_A=i*i+b*b;
        a[i].id_sub_A=i*i-b*b;
    }
sort(a+1,a+n+1,cmp1);
ll a1=a[1].id_add_A-a[n].id_add_A;
sort(a+1,a+n+1,cmp2);
ll a2=a[1].id_sub_A-a[n].id_sub_A;
cout<<max(a1,a2);


}
// 64 位输出请用 printf("%lld")

解题思路:保证|i**2-j**2|>=0的条件下,拆|Ai**2-Aj**2|绝对值,得到两种表达式

i**2+Ai**2-(j**2+Aj**2)和i**2-Ai**2-(j**2-Aj**2)

所以实际上就是分别求i**2+Ai**2和i**2-Ai**2四种最大值和最小值