SMU winter 2025 Personal Round 2

Problem - D - Codeforces

思路：

//在给定数中取x,y,z使得(x-y)^2+(y-z)^2+(z-x)^2最值.
//容易发现是找最接近的三个数字,但是怎么找呢
//经验总结(没想到是枚举中间那个),其中一个数字是枚举的(总是枚举中间那个,对于这个题中间那个就是中间大那个).剩下两个数字呢?--可以二分
//假设 x <= y <= z ; 那么可以枚举y,二分x和z;要在三个序列中都枚举y,并且x,z也要枚举两次.
//一共是3*n*2*logn次

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define sz(x) (int)x.size()
#define e emplace_back

int n[4];
int arr[4][100005];
int cal(int x,int y,int z){ return (x-y)*(x-y)+(y-z)*(y-z)+(z-x)*(z-x); }
int process(int i1,int i2,int i3){
    int res=LONG_LONG_MAX;
    for(int i=1;i<=n[i1];i++){
        int y=arr[i1][i];
        auto x1=upper_bound(arr[i2]+1,arr[i2]+n[i2]+1,y);
        auto y1=lower_bound(arr[i2]+1,arr[i2]+n[i2]+1,y);
        auto x2=upper_bound(arr[i3]+1,arr[i3]+n[i3]+1,y);
        auto y2=lower_bound(arr[i3]+1,arr[i3]+n[i3]+1,y);
        if(x1!=arr[i2]+1&&y2!=arr[i3]+n[i3]+1){
            int x=*prev(x1);
            int z=*y2;  //不用next
            res=min(res,cal(x,y,z));
        }
        if(x2!=arr[i3]+1&&y1!=arr[i2]+n[i2]+1){
            int x=*prev(x2);
            int z=*y1;  //不用next
            res=min(res,cal(x,y,z));
        }
    }
    return res;
}
//在给定数中取x,y,z使得(x-y)^2+(y-z)^2+(z-x)^2最值.
//容易发现是找最接近的三个数字,但是怎么找呢
//经验总结(没想到是枚举中间那个),其中一个数字是枚举的(总是枚举中间那个,对于这个题中间那个就是中间大那个).剩下两个数字呢?--可以二分
//假设 x <= y <= z ; 那么可以枚举y,二分x和z;要在三个序列中都枚举y,并且x,z也要枚举两次.
//一共是3*n*2*logn次
void solve(){       //D
    cin>>n[1]>>n[2]>>n[3];
    for(int i=1;i<=3;i++){
        for(int j=1;j<=n[i];j++){
            cin>>arr[i][j];
        }
        sort(arr[i]+1,arr[i]+n[i]+1);
    }
    int ans=LONG_LONG_MAX;
    ans=min(ans,process(1,2,3));
    ans=min(ans,process(2,1,3));
    ans=min(ans,process(3,1,2));
    cout<<ans<<endl;
}

int32_t main() {
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}