1： 暴力枚举两两之间点的距离。 O(n^2)；
2： 分治法。
与合并(归并)排序类似。 分解： 先把所有点按x 升序排序。 再取mid = (l+r) /2;
解决： 左右(返回d1,d2)两边分别递归下去，直到 1 或 2 可以直接返回值。 我们 取 mi = min(d1,d2); 表示当前最小的距离。
合并： 对于分开的两个区间，可能会存在着最短距离的两个点分别在分开的左右两边。所以我们要特殊处理这种情况。 我们按当前 l - r 的区间里面的点 按 y 升序排序(在这里我们可以运用归并排序的一部分进行合并)。以我们划分的点的x为中心线，把这个区间里面的点x轴距离中线小于m的加入到S里面。
接下来枚举每一个点，再枚举其它的任意一个点。算出距离(第二层循环证明它是小于等于6的)
证明如下，假设当前我们得到了这样一个区间，且当前处理的是这个点，则我们可以把它当作圆心，画出半径为d的圆，同时右边也可以画出一个矩形分成6个小矩形，这6个小矩形每个里面最多只会出现一个点（考虑两个点在一个小矩形的对角线处，长度也为5/6d，不会满足我们递归返回的最小值d），因为是按y从小到大排序，只会处理当前圆心点上方的点，下面画出极端情况后，一边就会有3个点需要遍历，左边也一样，所以左右边遍历点数最大为6。
这样基本操作复杂度为T(n) = 2T(n/2) + 6*n. -> T(n) = 6nlog(n)
具体看代码。
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #include<bits/stdc++.h> #define int long long using namespace std; typedef pair<int,int> pii; typedef long long ll; const int INF = 0x3f3f3f3f; const double eps = 1e-4; const int mod = 999911659; const int N = 200010; struct Node { double x,y; }; Node q[N],tmp[N]; bool cmpx(Node x,Node y) { return x.x < y.x; } #define C(A) ((A)*(A)) double dis(Node x,Node y) { return C(x.x-y.x) + C(x.y-y.y); } void merge(int l,int r,int mid){ int i = l,j = mid+1,cnt = l; while(i <= mid && j <= r){ if(q[i].y < q[j].y) tmp[cnt++] = q[i++]; else tmp[cnt++] = q[j++]; } while(i <= mid) tmp[cnt++] = q[i++]; while(j <= r) tmp[cnt++] = q[j++]; for(int i=l;i<=r;i++) q[i] = tmp[i]; } double closestpair(int l,int r){ if(l == r) return INF; if(l + 1 == r){ merge(l,r,l); return sqrt(dis(q[l],q[r])); } Node s[r-l+10]; int mid = (l+r)/2; int m = q[mid].x,cnt = 0; //先储存中点 double d1 = closestpair(l,mid); double d2 = closestpair(mid+1,r); double mi = min(d1,d2); // 分割线左右两边的距离<mi的点 merge(l,r,mid); // 用归并排序中的一部分进行按y排序 ，线性 // sort(q+l,q+r+1,cmpy); // 把中点周围 < mi的点全部加入到 s里面 for(int i=l;i<=r;i++){ if(fabs(q[i].x-m) < mi) s[cnt++] = q[i]; } mi = mi*mi; // 枚举部分，有证明说满足的点的个数会小于8个，所以是下面是线性的 for(int i=0;i<cnt-1;i++){ int k = i+1; while(k <= cnt-1 && C(s[k].y-s[i].y)<mi){//y差的平方小于就尝试一下 mi = min(mi,dis(s[k],s[i])); k ++; } } return sqrt(mi); } signed main(){ IOS; #ifdef ddgo freopen("C:/Users/asus/Desktop/ddgoin.txt","r",stdin); #endif int n; cin>>n; for(int i=0;i<n;i++){ double x,y; cin>>x>>y; q[i] = {x,y}; } sort(q,q+n,cmpx); cout<<fixed<<setprecision(4)<<closestpair(0,n-1)<<endl; return 0; }例题 ：洛谷p1257 洛谷p1492
