分治求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+10;
const int inf=1e18;
int n;
struct node{
    int x,y;
    bool operator <(const node &a)const{
        return this->x==a.x?this->y<a.y:this->x<a.x;
    }
}a[N];
struct Node{
    int x,y,id;
};
int calc(int lx,int ly,int rx,int ry){
    return abs(lx-rx)*abs(lx-rx)+abs(ly-ry)*abs(ly-ry);
}
vector<Node> e,e1,e2;
int solve(int l,int r,int num){
    if(l==r){
        if(num==1){
            e1.clear();
            e1.push_back({a[l].x,a[l].y,l});
        }
        else{
            e2.clear();
            e2.push_back({a[l].x,a[l].y,l});
        }
        return inf;
    }
    if(r-l==1){
        if(num==1){
            e1.clear();
            if(a[l].y>a[r].y||(a[l].y==a[r].y&&a[l].x<a[r].x)){
                e1.push_back({a[l].x,a[l].y,l});
                e1.push_back({a[r].x,a[r].y,r});
            }
            else{
                e1.push_back({a[r].x,a[r].y,r}); 
                e1.push_back({a[l].x,a[l].y,l});
            }
        }
        else{
            e2.clear();
            if(a[l].y>a[r].y||(a[l].y==a[r].y&&a[l].x<a[r].x)){
                e2.push_back({a[l].x,a[l].y,l});
                e2.push_back({a[r].x,a[r].y,r});
            }
            else{
                e2.push_back({a[r].x,a[r].y,r});   
                e2.push_back({a[l].x,a[l].y,l});
            }
        }
        return calc(a[l].x,a[l].y,a[r].x,a[r].y);
    }
    int mid=(l+r)>>1;
    int ansl=solve(l,mid,1);
    vector<Node> ee1;
    ee1=e1;
    int ansr=solve(mid+1,r,2);
    e.clear();
    int i,j;
    for(i=0,j=0;i<ee1.size()&&j<e2.size();){
        if(ee1[i].y>e2[j].y||(ee1[i].y==e2[j].y&&ee1[i].x<e2[j].x)) e.push_back(ee1[i]),i++;
        else e.push_back(e2[j]),j++;
    }
    while(i<ee1.size()){
        e.push_back(ee1[i]);
        i++;
    }
    while(j<e2.size()){
        e.push_back(e2[j]);
        j++;
    }
    int h=min(ansl,ansr);
    int ll=mid,rr=mid+1;
    while(a[mid].x-a[ll].x<h&&ll>l) ll--;
    while(a[rr].x-a[mid+1].x<h&&rr<r) rr++;
    vector<Node> v;
    v.clear();
    for(int i=0;i<e.size();i++){
        if(e[i].id>=ll&&e[i].id<=rr){
            v.push_back(e[i]);
        }
    }
    // cerr<<l<<' '<<r<<'\n';
    for(int i=0;i<v.size();i++){
        // int cnt=0;
        int xx=v[i].x,yy=v[i].y;
        for(int j=i+1;j<v.size();j++){
            if(yy-v[j].y>=h) break;
            // cnt++;
            h=min(h,calc(xx,yy,v[j].x,v[j].y));
        }
        // cerr<<cnt<<' ';
    }
    // cerr<<'\n';
    if(num==1){
        e1.clear();
        e1=e;
    }
    else{
        e2.clear();
        e2=e;
    }
    return h;
}
signed main(){
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1);
    int res=solve(1,n,1);
    cout<<res<<'\n';
}