给定平面上\(n\;(n\leq10^6)\)个点，求所有点对中最近点对的距离。
首先朴素做法是\(O(n^2)\)的，而朴素做法之所以慢是因为把很多根本不可能成为最近点对的点对计算了距离，比如下图：

朴素算法的瓶颈在于计算像1-6这样的点对，那么怎么尽量减少这样的计算呢？
不过首先摆在我们眼前的问题是要能够“确定”1-6的不合法，首先很容易想到对x排序，然后从左往右一个个枚举左端点，再一个个枚举右端点，直到x的差超过当前的ans/mindis就break。
P1429 平面最近点对（超级弱化版）

#include <bits/stdc++.h>
#define ri register int
using namespace std;
const int maxn=200010;const double inf=1.0/0.0;
struct VT{double x,y;}p[maxn];
int n,m,c[maxn];
inline bool cmp1(const VT &a,const VT &b){return a.x<b.x;}
inline void setmin(double &a,double b){if(a>b)a=b;}
inline double getdis(int a,int b){
	double x=p[a].x-p[b].x,y=p[a].y-p[b].y;
	return sqrt(x*x+y*y);
}
int main(){
	scanf("%d",&n);
	for(ri i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
	sort(p+1,p+1+n,cmp1);
	double ans=inf;
	for(ri i=1;i<=n;i++){
		for(ri j=i+1;j<=n&&p[j].x-p[i].x<ans;j++){
			setmin(ans,getdis(i,j));
		}
	}
	printf("%.4lf\n",ans);
	return 0;
}

就这？
不得不说这题数据实在是太水了，如果构造一种像这样的情况

就是让让答案足够大，相邻两点的横坐标之差尽量小，这样就可以卡掉上面这个复杂度不正确的算法。
（不过即使如此，也可以通过把所有点绕原点旋转某个角度这种玄学的方法来防止被卡，实测快1000多倍）
当然我们还是需要一个正确时间复杂度的算法！（虽然常数大得可以）
回想一下刚才朴素优化算法的问题：只是限制了相对的x小于mindis，没有限制相对的y，那么有什么方法既限制x又限制y呢？那么一种比较好写而且保证复杂度的方法就是——分治。
如果现在已经求出\([l,mid]\)和\([mid+1,r]\)两个子区间内部的最短点对距离，那么现在就只用考虑一个端点在左区间，一个端点在右区间的情况，这个时候再来限制x和y就非常方便了！挑出距两个区间分界线不超过mindis的所有点，再对y进行排序。
不妨考虑，在每次合并子区间的过程中，左区间中的每个点个点最多与右区间中的6个点计算距离！
这是因为在合并当前区间之前，右区间的最近点对就算进答案里了。换句话说，右区间任意两点距离不小于mindis。
最后上代码（注意回溯边界）

#include <bits/stdc++.h>
#define ri register int
using namespace std;
const int maxn=200010;const double inf=1.0/0.0;
struct VT{double x,y;}p[maxn];
int n,m,c[maxn];double ans=inf;
inline bool cmp1(const VT &a,const VT &b){return a.x<b.x;}
inline bool cmp2(int a,int b){return p[a].y<p[b].y;}
inline void setmin(double &a,double b){if(a>b)a=b;}
inline double getdis(int a,int b){
	double x=p[a].x-p[b].x,y=p[a].y-p[b].y;
	return sqrt(x*x+y*y);
}
void solve(int l,int r){
	if(l==r)return;
	if(l+1==r)return setmin(ans,getdis(l,r));
	int mid=(l+r)>>1;
	solve(l,mid);solve(mid+1,r);m=0;
	for(ri i=l;i<=r;i++)if(fabs(p[i].x-p[mid].x)<ans)c[++m]=i;
	sort(c+1,c+1+m,cmp2);
	for(ri i=1;i<=m;i++){
		for(ri j=i+1;j<=m&&p[c[j]].y-p[c[i]].y<ans;j++){
			setmin(ans,getdis(c[i],c[j]));
		}
	}
}
int main(){
	scanf("%d",&n);
	for(ri i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
	sort(p+1,p+1+n,cmp1);solve(1,n);
	printf("%.4lf\n",ans);
	return 0;
}