本文全文原创 转载请注明出处
http://blog.csdn.net/lytning/article/details/25370169
平面最近点对，即平面中距离最近的两点
分治算法：
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);