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

主要思路：

分治，将点按横坐标为第1关键字升序排列，纵坐标为第2关键字升序排列，进入左半边和右半边进行分治。

设d为左右半边的最小点对值。然后以mid这个点为中心，扩展宽为2d，长为2d的正方形。除了这个正方形外的点都不可能使答案更小。而且这个正方形里至多8个点（可以证明至多6个，我不会。but，知道至多8个就够了，这样已经保证了复杂度。）一句话证明：如果多余8个点，那么必有2个点的最小距离比d小。这8个点内暴力枚举就好了。

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=1000005;

const double inf=1e12;

struct node{

	double x,y;

}p[N];

bool cmp(node a,node b)

{

	if(a.x==b.x)return a.y<b.y;

	return a.x<b.x;

}

bool cmp2(int a,int b)

{

	return p[a].y<p[b].y;

}

double dist(int a,int b){return sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y));}

int n,a[N];

double msort(int l,int r)

{

	double d=inf;

	if(l==r)return d;

	if(l==r-1)return dist(l,r);

	int mid=l+r>>1;

	double d1=msort(l,mid);

	double d2=msort(mid+1,r);

	d=min(d1,d2);

	int cnt=0;

	for(int i=l;i<=r;i++)

		if(fabs(p[i].x-p[mid].x)<=d)a[++cnt]=i;

	sort(a+1,a+cnt+1,cmp2);

	for(int i=1;i<=cnt;i++)

	{

		for(int j=i+1;j<=cnt&&fabs(p[a[i]].y-p[a[j]].y)<d;j++)

		{

			d=min(d,dist(a[i],a[j]));

		}

	}

	return d;

}

signed 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\n",msort(1,n));

	return 0;

}

巴特西

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

最新文章

热门文章