djwj323 @ 2022-05-31 15:34:45
#include<bits/stdc++.h>
using namespace std;
struct node{
long long x,y;
}z[400003];
int n,i;
long long w(node A,node B){return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}
bool cmp(node A,node B){return A.x==B.x?A.y<B.y:A.x<B.x;}
bool cmp_PLUS(int A,int B){return z[A].y<z[B].y;}
long long s(int l,int r){
if(l==r) return 1e18;
if(l==r-1) return w(z[l],z[r]);
int mid=(l+r)/2,p[400003],t=0;
long long ans=min(s(l,mid),s(mid+1,r)),c=sqrt(ans);
for(int i=l;i<=r;i++)
if(abs(z[i].x-z[mid].x)<=c) p[++t]=i;
sort(p+1,p+t+1,cmp_PLUS);
for(int i=1;i<=t;i++)
for(int j=i+1;j<=t&&z[p[j]].y-z[p[i]].y<c;j++) ans=min(ans,w(z[p[i]],z[p[j]])),c=sqrt(ans);
return ans;
}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++) scanf("%lld%lld",&z[i].x,&z[i].y);
return sort(z+1,z+n+1,cmp),printf("%lld",s(1,n)),0;
}
//YuKai AK CSP
//YuKai AK NOIP
//YuKai AK NOI
//YuKai AK IOI
//YuKai AK ZJOI2022
by Iwara_qwq @ 2022-05-31 15:40:56
卡精度,当时我答案差1,加上0.1之后取个整就过了
by djwj323 @ 2022-05-31 15:54:53
已过