平面最近点对

分治本身的大部分内容还是比较好想的，就是中线划分的左右区间可能出现跨线最小值的操作，所以说我们需要枚举另一个点集.也就是距离中线的距离小于d的点，因为这些才是有可能在更新答案的点集，然后我们再把他们按照y排序枚举看一下如果y差值都大于d那么就不枚举这是一个剪枝，剩下的就是更新答案，然后就ok了 O(NlogN)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll re[200005],p=0;
struct node
{
	double x,y;
}a[200005];
double dis(ll x,ll y)
{
	return sqrt((a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y));
}
bool cmp(node a,node b)
{
	return a.x<b.x;
}
bool cmp2(ll aa,ll bb)
{
	return a[aa].y<a[bb].y;
}
double merge(ll l,ll r)
{
	if(l==r)
	return 1<<30;
	if(l+1==r)
	return dis(l,r);
	int mid=(l+r)>>1;
	double d1=merge(l,mid);
	double d2=merge(mid+1,r);
	double d=min(d1,d2);
	p=0;
	for(int i=l;i<=r;i++)
	if(fabs(a[mid].x-a[i].x)<d)
	re[++p]=i;
	sort(re+1,re+1+p,cmp2);
	for(int i=1;i<=p;i++)
	for(int j=i+1;j<=p&&fabs(a[re[j]].y-a[re[i]].y)<d;j++)
	d=min(dis(re[j],re[i]),d);
	return d;
}
int main()
{
	ll n;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	scanf("%lf%lf",&a[i].x,&a[i].y);
	sort(a+1,a+1+n,cmp);
	printf("%.4f",merge(1,n));
}