c语言算法 - 分而治之算法 - 距离最近的点对

核心提示：程序14-9 计算两点距离templateinline float dist(const T& u, const T& v){ / /计算点u 和v之间的距离float dx = u.x-v. x ;float dy = u.y-v. y ;return sqrt(dx * dx + dy * dy);}如果点的数目少

程序14-9 计算两点距离

template
inline float dist(const T& u, const T& v)
{ / /计算点u 和v之间的距离
float dx = u.x-v. x ;
float dy = u.y-v. y ;
return sqrt(dx * dx + dy * dy);
}

如果点的数目少于两个，则函数c l o s e s t (见程序1 4 - 1 0 )返回f a l s e，如果成功时函数返回t r u e。当函数成功时，在参数a 和b 中返回距离最近的两个点，在参数d 中返回距离。代码首先验证至少存在两点，然后使用M e rg e S o r t函数(见程序14-3) 按x 坐标对X中的点排序。接下来把这些点复制到数组Y中并按y 坐标进行排序。排序完成时，对任一个i，有Y [i ] . y≤Y [i+ 1 ] . y，并且Y [i ] .p给出了点i 在X中的位置。上述准备工作做完以后，调用函数close (见程序1 4 - 11 )，该函数实际求解最近点对。

程序14-10 预处理及调用c l o s e

bool closest(Point1 X[], int n, Point1& a, Point1& b, float& d)
{// 在n >= 2个点中寻找最近点对
// 如果少于2个点，则返回f a l s e
// 否则，在a 和b中返回距离最近的两个点
if (n < 2) return false;
// 按x坐标排序
M e r g e S o r t ( X , n ) ;
// 创建一个按y坐标排序的点数组
Point2 *Y = new Point2 [n];
for (int i = 0; i < n; i++) {
// 将点i 从X 复制到Y
Y[i].p = i;
Y[i].x = X[i].x;
Y[i].y = X[i].y;
}
M e r g e S o r t ( Y,n); // 按y坐标排序
// 创建临时数组
Point2 *Z = new Point2 [n];
// 寻找最近点对
c l o s e ( X , Y, Z , 0 , n - 1 , a , b , d ) ;
// 删除数组并返回
delete [] Y;
delete [] Z;
return true;
}