编程之美2.11――寻找最近点对（POJ 3714）(一)

问题：
给定平面上N个点的坐标，找出距离最近的两个点。

解法：
我们先对N个点的x坐标进行排序，排序我们使用最坏复杂度O(n*logn)的快速排序方法，在排序的过程中minDifferent会递归计算出左右两边的最小距离，再用其中的较小值minum得到以中位数点附近的带状区域[p[median+1].x-median, p[median].x+median]，对带状区域的点按照y坐标排序，对带状区域的每个点只需计算最多7个点，就能得到所有可能小于minum的点对。
[cpp]
#include
#include
#include
#include
using namespace std;

// 顶点信息
struct Point
{
double m_x, m_y;
Point():m_x(0.0),m_y(0.0) {}
Point(double x, double y):m_x(x),m_y(y){}
bool operator==(const Point& p) const
{return m_x==p.m_x && m_y==p.m_y;}
};

ostream& operator<<(ostream& os, const Point& p)
{
return os << "(" << p.m_x << "," << p.m_y << ")";
}

// 插入排序
template
void insert_sort(vector &vec, int l, int r, Pr pred)
{
int i, j;
for (i=l+1; i<=r; i++)
{
T tmp = vec[i];
for (j=i-1; j>=l && pred(tmp,vec[j]); j--)
vec[j+1]=vec[j];
vec[j+1] = tmp;
}
}

// 找到key所在的位置
template
int get_position(vector &vec, int l, int r, T key)
{
for (int i=l; i<=r; i++)
if (key == vec[i])
return i;
return -1;
}

// 按第一个元素对vec进行划分
template
int partition(vector &vec, int l, int r, Pr pred)
{
int i, j;
for (i=l+1,j=l; i<=r; i++)
{
if (pred(vec[i],vec[l]))
{
++j;
swap(vec[i],vec[j]);
}
}
swap(vec[j],vec[l]);
return j;
}

// 顺序统计得到第k个元素的值
template
T select(vector &vec, int l, int r, int k, Pr pred)
{
int n = r-l+1;
if (n==1)
{
if (k!=0)
printf("Out of Boundary!\n");
return vec[l];
}
// 找中位数的中位数作为分割点
int cnt = n/5;
int tcnt = (n+4)/5;
int rem = n%5;