用分治法，理论复杂度 O(nlogn) 合并的时候在 y 方向上做归并排序，然后 st 左右交替存 mid 左右范围内的，理论复杂度应该没问题。

看这道题的时限是350ms，用一个乱搞的做法都有148分（就是分治法不做在y方向归并排序的优化，而是暴力双层for）

所以很困惑是不是有点卡常

代码丑，可以不看（只想问问有没有也是分治法理论 nlogn 被卡的

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

namespace Basis2D{
    constexpr double PI = acosl(-1.);
    constexpr double INF = 1e20;
    constexpr double EPS = 1e-12;
    struct Point{
        double x,y;
        Point(double _x=0, double _y=0):x(_x),y(_y){}
        Point& operator=(const Point&o){
            x = o.x; y = o.y;
            return *this;
        }
        friend std::ostream& operator<<(std::ostream&out, const Point&p){
            return out<<'('<<p.x<<','<<p.y<<')';
        }
        bool operator<(const Point&o)const{
            return x==o.x?y<o.y:x<o.x;
        }
        Point operator+(const Point&o)const{
            return {x+o.x,y+o.y};
        }
        Point operator-()const{
            return {-x,-y};
        }
        Point operator-(const Point&o)const{
            return (*this) + (-o);
        }
        double operator*(const Point&o)const{
            return dot(o);
        }
        bool operator==(const Point&o)const{
            return between(o,o);
        }
        double norm()const{
            return sqrt((*this) * (*this));
        }
        double dot(const Point&o)const{
            return x*o.x+y*o.y;
        }
        double cross(const Point&o)const{
            return x*o.y-y*o.x;
        }
        bool between(Point a,Point b)const{
            if(abs((a.x-x)*(b.y-y)-(b.x-x)*(a.y-y))>EPS)return false;
            if(a.x>b.x)std::swap(a.x,b.x);
            if(a.y>b.y)std::swap(a.y,b.y);
            return a.x-EPS<=x&&x<=b.x+EPS &&
                a.y-EPS<=y&&y<=b.y+EPS;
        }
        double theta()const{
            return x+y?atan2(y,x):-INF;
        }
    };
    using Points = std::vector<Point>;
}


namespace Algorithm2D{
    using namespace Basis2D;
    std::pair<int,int> closet_pair(const Points&dots){
        typedef std::pair<int,int> resultType;
        std::vector<int> sorted(dots.size());
        std::iota(sorted.begin(),sorted.end(),0);
        sort(sorted.begin(),sorted.end(),[&dots](auto a,auto b){
            return dots[a] < dots[b];
        });
        resultType res;
        double resv = INF;
        function<void(int,int)> rec = [&](int l,int r){
            if(r-l<=6){
                for(int i=l;i<r;i++){
                    for(int j=l;j<i;j++){
                        double tmp = (dots[sorted[i]]-dots[sorted[j]]).norm();
                        if(tmp<resv)resv=tmp,res={sorted[i],sorted[j]};
                    }
                }
                std::sort(sorted.begin()+l,sorted.begin()+r,[&dots](auto a,auto b){
                    return dots[a].y < dots[b].y;
                });
            }else{
                int mid = (l+r) / 2;
                auto&middot = dots[sorted[mid]];
                rec(l, mid); rec(mid, r);
                std::inplace_merge(sorted.begin()+l,sorted.begin()+mid,sorted.begin()+r,[&dots](auto a,auto b){
                    return dots[a].y < dots[b].y;
                });

                std::array<std::vector<int>, 2> st;
                for(int i=l;i<r;i++){
                    auto&dot = dots[sorted[i]];
                    if(abs(dot.x-middot.x)>resv)continue;
                    bool lr = dot < middot;
                    for(auto it=st[lr].rbegin();it!=st[lr].rend()&&dots[*it].y+resv>=dot.y;it++){
                        double tmp = (dot-dots[*it]).norm();
                        if(tmp<resv)resv=tmp,res={sorted[i],*it};
                    }
                    st[!lr].push_back(sorted[i]);
                }
            }
        };
        rec(0, dots.size());
        return res;
    }
}

signed main(){
    int n;cin>>n;

    using namespace Basis2D;
    Points dots(n);
    for(auto&[x,y]:dots)cin>>x>>y;

    auto p = Algorithm2D::closet_pair(dots);
    double ansx = (dots[p.first]-dots[p.second]).x;
    double ansy = (dots[p.first]-dots[p.second]).y;
    cout<<setprecision(0)<<fixed<<(ansx*ansx+ansy*ansy)<<endl;

    return 0;
}