计算几何 平面不久前点对 nlogn分治算法 求平面中距离最近的两点
本文全文原创 转载请注明出处
平面最近点对，即平面中距离最近的两点
分治算法：
int SOLVE(int left,int right)//求解点集中区间[left,right]中的最近点对
{
double ans; //answer
0) 调用前的预处理:对所有点排序,以x为第一关键词y为第二关键字 , 从小到大;
1) 将所有点按x坐标分成左右两部分;
/* 分析当前集合[left,right]中的最近点对，有两种可能：
1. 当前集合中的最近点对，点对的两点同属于集合[left,mid]或同属于集合[mid,right]
则ans = min(集合1中所有点的最近距离, 集合2中所有点的最近距离)
2. 当前集合最近点对中的两点分属于不同集合：[left,mid]和[mid,right]
则需要对两个集合进行合并，找出是否存在p∈[left,mid],q∈[mid,right],使得distance(p,q)小于当前ans(即步骤1中求得的ans);
*/
2) Mid = (left+right)/2;
ans = min( SOLVE(left,mid), SOLVE(mid,right) );
即：递归求解左右两部分中的最近距离，并取最小值；
//此步骤实现上文分析中的第一种情况
/*
再次进行分析
我们将集合[left,right]用x = mid这条直线分割成两部分
则如果画出直线l1:x=mid-ans 和 l2:x=mid+ans，显然如果有p∈[left,mid], q∈[mid,right]且distance(p,q) < ans则p,q一定在直线l1和直线l2之间，否则distance(p,q)必定大于ans。
于是扫描出在l1和l2之间的点
*/
3) 建立缓存数组temp[];
for i = left TO right
{
如果 abs(Point[i].x - Point[mid].x) <= ans
则向temp中加入点Point[i];
}
/*
对于temp中的点，枚举求所有点中距离最近两点的距离，然后与ans比较即可。
枚举的时候不必两两枚举。观察下图中的点p
于是我们可以对temp以y为唯一关键字从小到大排序,进行枚举, 更新ans,然后在枚举时判断：一旦枚举到的点与p点y值之差大于ans，停止枚举。最后就能得到该区间的最近点对。
*/
4) sort(temp);
for i = 0 TO k-1
{
for j = i+1 TO k-1
如果 temp[j].y - temp[i].y >= ans break;
ans = min( ans, distance(temp[i], temp[j]) );
}
5) return ans;
}
算法的时间复杂度
由鸽巢原理，代码中第四步的枚举实际上最多只会枚举6个点，效率极高
本算法时间复杂度为O(n log n)
代码：
//是vijos1012的ac代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps = 1e-8;
const int INF = 0x7fffffff;
int n;
struct Point
{
double x,y;
Point(double x=0, double y=0):x(x),y(y) {}
bool operator < (const Point& p) const
{
if(x != p.x) return x < p.x;
else return y < p.y;
}
}p[200000+5],temp[200000+5];
bool cmpy(Point a, Point b)
{
return a.y < b.y;
}
double Dis(Point a, Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
double Closest_Pair(int left, int right)
{
double d = INF;
if(left == right)
return d;
if(left +1 == right)
return Dis(p[left],p[right]);
int mid = (left+right)>>1;
double d1 = Closest_Pair(left,mid);
double d2 = Closest_Pair(mid,right);
d = min(d1,d2);
int k = 0;
for(int i = left; i <= right; i++)
{
if(fabs(p[mid].x - p[i].x) <= d)
temp[k++] = p[i];
}
sort(temp,temp+k,cmpy);
for(int i = 0; i < k; i++)
{
for(int j = i+1; j < k && temp[j].y - temp[i].y < d; j++)
{
double d3 = Dis(temp[i],temp[j]);
d = min(d,d3);
}
}
return d;
}
int main()
{
cin>>n;
for(int i=0; i<n; i++)
{
double a,b;
scanf("%lf%lf",&a,&b);
p[i] = Point(a,b);
}
sort(p,p+n);
printf("%.3f",Closest_Pair(0,n-1));
}
练习题：
vijos1012 https://vijos.org/p/1012
裸题，平面最近点对（虽然本题暴力也能过=。=）
poj 3714 http://poj.org/problem?id=3714
大意：给出平面中的两类点，求平面最近点对，要求该点对中的两点不是同类点