这是一篇决策单调性题解，好像现在还没有相同做法的题解。
还是类似的分治方式，每次点分成左右两半求两边贡献，再处理跨区间贡献。
但是有一种新的处理贡献方式：决策单调性。
先将两边点各自按照纵坐标升序排序，然后对每个左半边的点找最近的点。怎么找呢？考虑设置两个指针，分别指向纵坐标升序的左边第 \(i\) 个点和右边第 \(j\) 个点，满足 \(y_j\leq y_i\)。再用一个单调队列维护右边可能是目标点的点。容易发现这个单调队列里的点满足 \(x_{q_k}>x_{q_{k-1}}\)，因为到左边第 \(i\) 个点纵坐标距离一定是单调递减的，如果再有 \(x_{q_k}\le x_{q_{k-1}}\)，那第 \(k-1\) 个元素就一定会被弹出了。具体可以结合下图理解：
然后就要证明决策单调性了，也就是说，如果 \(dis(i,q_k)\ge dis(i,q_{k+1})\)，那么 \(q_k\) 以后都不可能比 \(q_{k+1}\) 优。
证明：如上图，已知 \(a>b\)，又 \(b+c>d+a\)（可用三角形两边之和大于第三边证），所以一定有 \(d<c\)，得证。
于是可以对每个 \(i\) 找到最近的点，不断更新答案即可。
按升序做完，还要按降序再做一遍，不断递归求解即可。
如果用 sort，时间复杂度为 \(O(n\log^2n)\)，但是常数较大，无法通过，于是直接用归并完成纵坐标的排序，复杂度降到 \(O(n\log n)\)，可以通过。
code：
点击查看代码
int n,m,q[N];
struct node{
int x,y;
}e[N],d[N];
ll ans=1e18;
inline bool cmp1(node x,node y){
return x.x<y.x;
}
inline bool cmp2(node x,node y){
return x.y<y.y;
}
inline ll dis(node i,node j){
return 1ll*(i.x-j.x)*(i.x-j.x)+1ll*(i.y-j.y)*(i.y-j.y);
}
void divide(int l,int r){
if(l==r)
return;
int mid=(l+r)>>1;
divide(l,mid);
divide(mid+1,r);
int L=1,R=0;
for(int i=l,j=mid;i<=mid;i++){
while(j<r&&e[j+1].y<=e[i].y){
j++;
while(L<=R&&e[q[R]].x>=e[j].x)
R--;
q[++R]=j;//单调队列操作
}
while(L<R&&dis(e[i],e[q[L+1]])<=dis(e[i],e[q[L]]))
L++;//决策单调性
if(L<=R)
ans=min(ans,dis(e[i],e[q[L]]));
}//升序做一遍
L=1,R=0;
for(int i=mid,j=r+1;i>=l;i--){
while(j>mid+1&&e[j-1].y>=e[i].y){
j--;
while(L<=R&&e[q[R]].x>=e[j].x)
R--;
q[++R]=j;
}
while(L<R&&dis(e[i],e[q[L+1]])<=dis(e[i],e[q[L]]))
L++;
if(L<=R)
ans=min(ans,dis(e[i],e[q[L]]));
}//倒过来再做一遍
int p=l,q=mid+1,k=l;
while(p<=mid&&q<=r){
if(e[q].y<e[p].y)
d[k++]=e[q++];
else
d[k++]=e[p++];
}
while(p<=mid)d[k++]=e[p++];
while(q<=r)d[k++]=e[q++];
for(int i=l;i<=r;i++)e[i]=d[i];//归并，从逆序对贺过来的
}
void solve(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
e[i]={read(),read()};
sort(e+1,e+n+1,cmp1);
divide(1,n);
printf("%lld\n",ans);
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
solve();
}