洛谷P1429 平面最近点对 几何 模板

给出平面上若干个点，求最近的两点之间的距离。
直接暴力枚举两个点求最短的距离，时间复杂度是$O(n^2)$O(n2)。
这里尝试利用已经有的最短距离来实现剪枝优化：首先，对平面上所有的点按照横坐标排序，横坐标相等的按照纵坐标来排序。然后考虑中间这个点的位置，所有的点对分为两类，一类是全部在左边或者右边的区间，另外一类横跨中间的这个点。对于前一种类型，分治递归解决。并且我们取$d=min(d1,d2)$d=min(d1,d2)，这是我们已经求出的最短距离。那么显然此时我们对于那些横坐标和中间点的横坐标差值大于$d$d的所有的点不再考虑。对于剩下来的点，我们再按照纵坐标排序，纵坐标相同的按照横坐标排序。然后枚举点对，并且在枚举的过程中更新最短距离和剪枝。
可以被证明中间的剪枝的操作对复杂度的贡献是一个较小的常数。
所以分治的复杂度是线性的$O(n)$O(n)，加上一开始的排序是$O(nlogn)$O(nlogn)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll INF=LONG_LONG_MAX;
const int N=2e5+7; 
struct Point {
	double x,y;
}a[N],b[N];
bool cmp1(Point a,Point b) {
	if(a.x<b.x) return 1;
	else if(a.x==b.x&&a.y<b.y) return 1;
	else return 0; 
} 
bool cmp2(Point a,Point b) {
	if(a.y<b.y) return 1;
	else if(a.y==b.y&&a.x<b.x) return 1;
	else return 0;
}
double cal(Point a,Point b) {
	double dx=a.x-b.x;
	double dy=a.y-b.y;
	return sqrt(dx*dx+dy*dy);
}
double merge(int l,int r) {
	if(l==r) return 2e9;
	else if(r-l==1) return cal(a[l],a[r]);
	int mid=(l+r)>>1;
	double d=min(merge(l,mid),merge(mid+1,r));
	int tot=0;
	for(int i=l;i<=r;i++) {
		if(fabs(a[i].x-a[mid].x)<=d)   
			b[++tot]=a[i];
	}
	sort(b+1,b+1+tot,cmp2);
	for(int i=1;i<=tot;i++) {
		for(int j=i+1;j<=tot;j++) {
			if(b[j].y-b[i].y>=d) break;
			d=min(d,cal(b[i],b[j]));
		}
	}
	return d;
}
int main() {
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) 
		scanf("%lf%lf",&a[i].x,&a[i].y);
	sort(a+1,a+1+n,cmp1);
	printf("%0.4lf\n",merge(1,n));
	return 0;
}