【分治】P1429 平面最近点对（加强版）

给定平面上n个点，找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的

 

将每个带求的区间分成左右两部分来处理，当前已知左和右的最小距离，那么只需要与跨过分界线的距离比较即可！

分而治之，分很好处理，这个合并设计到几处比较的过程

设minn为左右半边的最小点对值。

然后以mid这个点为中心，扩展宽为2minn，长为2minn的正方形。

除了这个正方形外的点都不可能使答案更小。

 

 

代码

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
double inf=1e18;
ll n;
struct point 
{
	double x,y;
}p[maxn];
bool cmp(point aa,point bb)
{
	if(aa.x!=bb.x) return aa.x<bb.x;
	return aa.y<bb.y;
}
double calc(int x,int y)
{
	return sqrt((p[x].x-p[y].x)*(p[x].x-p[y].x)+(p[x].y-p[y].y)*(p[x].y-p[y].y));
}
ll s[maxn];
bool CMP(int x,int y)
{
	return p[x].y<p[y].y;
}
double solve(int l,int r)
{
	double d=inf;
	ll mid=l+r>>1;
	if(l==r) return d;
	if(l+1==r) return calc(l,r);
	double d1=solve(l,mid);
	double d2=solve(mid+1,r);
	d=min(d,d1); d=min(d,d2);
	int cnt=0;
	for(int i=l;i<=r;i++)
		if(abs(p[i].x-p[mid].x)<=d) 
			s[++cnt]=i;
	sort(s+1,s+cnt+1,CMP);
	for(int i=1;i<=cnt;i++)
		for(int j=i+1;j<=cnt && abs(p[s[i]].y-p[s[j]].y)<d;j++)
			d=min(d,calc(s[i],s[j]));
	return d;
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
    sort(p+1,p+n+1,cmp);
    printf("%.4lf",solve(1,n));
    return 0;
}