先证明这个最多6个
我们将\(d \times 2d\)的长方形划分成6个\(\frac{1}{2}d \times \frac{2}{3}d\)的小长方形，根据抽屉原理，如果大于6个点，那么至少有两个点在同一个小长方形里面，然而小长方形里面的距离最长是体对角线\(\frac{5}{6}d\)，所以矛盾，于是原结论正确
以上算法的时间复杂度是\(O(nlog^2n)\)，因为最多分成\(logn\)层，每一层点的总数是\(n\)，但是加上排序就会带上log
所以瓶颈是排序，我们想办法消除掉这个排序
一旦有了分治+排序，我们就可以想到利用归并排序的思想来消除复杂度
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=4e5+10;
int n;
struct Node
{
ll x,y;
}temp[N],w[N];
int read()
{
int x=0,f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-f;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-48;s=getchar();}
return x*f;
}
bool cmp(Node i,Node j)
{
return i.x<j.x;
}
ll dis(Node i,Node j)
{
return (i.x-j.x)*(i.x-j.x)+(i.y-j.y)*(i.y-j.y);
}
ll cal(int l,int r)
{
if(l==r) return 1e16;
int mid=l+r>>1,cnt=0;
ll Midx=w[mid].x;
ll d=min(cal(l,mid),cal(mid+1,r));
int i=l,j=mid+1;
while(i<=mid||j<=r)
{
while(i<=mid&&(ll)abs(w[i].x-Midx)*abs(w[i].x-Midx)>=d)
i++;
while(j<=r&&(ll)abs(w[j].x-Midx)*abs(w[j].x-Midx)>=d)
j++;
if(i<=mid)
{
if(j<=r)
{
if(w[i].y<w[j].y) temp[++cnt]=w[i++];
else temp[++cnt]=w[j++];
}
else temp[++cnt]=w[i++];
}
else if(j<=r) temp[++cnt]=w[j++];
}
for(int i=1;i<cnt;i++)
for(int j=i+1;j<=cnt&&(temp[j].y-temp[i].y)*(temp[j].y-temp[i].y)<d;j++)
d=min(d,dis(temp[i],temp[j]));
i=l,j=mid+1;
int k=l;
while(i<=mid&&j<=r)
{
if(w[i].y<w[j].y) temp[k++]=w[i++];
else temp[k++]=w[j++];
}
while(i<=mid) temp[k++]=w[i++];
while(j<=r) temp[k++]=w[j++];
for(int i=l;i<=r;i++)
w[i]=temp[i];
return d;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
w[i].x=read(),w[i].y=read();
sort(w+1,w+n+1,cmp);
printf("%lld",cal(1,n));
return 0;
}