题意

• 给定若干个点，求最近的两个点的距离

思路

• 分治

• 对于所有点，总可以按照以下三种情况处理：

  1.只剩下两个点：直接返回两点距离

  2.只剩下三个点：返回三个距离的最小值

  3.剩下的点超过三个，从中点分开，不断递归至情况一/情况二

• 由此，总能不断地把大区间二分成小区间，并算出区间内最近点对距离dis

• 此后，考虑将区间合并，找出可能的在跨区间的最小点对：

  1.记录全部距离mid的距离小于等于dis的点

  2.将这些点按纵坐标排序

  3.二重循环遍历所有点，如果两个点的纵坐标差值大于dis，直接跳出循环，进行剪枝

• 最后将所有答案整合求最小即可得到答案

AC代码

#include <bits/stdc++.h>
#define ll long long 
using namespace std;

typedef struct{
	ll x,y;
}dot;
int b[404040];
dot a[404040];

int cmpx(dot a,dot b){return a.x<b.x;}
int cmpy(int j,int k){return a[j].y<a[k].y;}

ll dis(dot p,dot q){
	return 	(p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y);
}

ll deal(int l,int r){
	ll rst;
	if(l+1==r)return dis(a[l],a[r]);
	if(l+2==r)return min(min(dis(a[l],a[r]),dis(a[l+1],a[r])),dis(a[l],a[l+1]));
	int mid=(l+r)>>1;
	rst=min(deal(l,mid),deal(mid+1,r));
	int cnt=0;
	for(int i=l;i<=r;i++){
		if(abs(a[i].x-a[mid].x)<=rst){
			b[cnt++]=i;
		}
	}
	sort(b,b+cnt,cmpy);
	for(int i=0;i<cnt-1;i++){
		for(int j=i+1;j<cnt;j++){
			if(a[b[j]].y-a[b[i]].y>=rst)break;
			rst=min(rst,dis(a[b[j]],a[b[i]]));
		}
	}
	return rst;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		for(int i=0;i<n;i++){
			scanf("%lld%lld",&a[i].x,&a[i].y);
		}
		sort(a,a+n,cmpx);
		ll ans=deal(0,n-1);
		printf("%lld\n",ans);
	}
}