新建 文本文档 (2).txt

对蛮力算法的看法...大家分析一下哈

class Point1 { 

friend float dist(const Point1&, const Point1&); 

friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&, Point1&, float&); 

friend bool closest(Point1 *, int, Point1&, Point1&,float&); 

friend void main(); 

p u b l i c : 

int operator<=(Point1 a) const 

{return (x <= a.x);} 

p r i v a t e : 

int ID; // 点的编号 

float x, y; // 点坐标 

} ; 

class Point2 { 

friend float dist(const Point2&, const Point2&); 

friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&, Point1&, float&); 

friend bool closest(Point1 *, int, Point1&, Point1&, float&);


friend void main(); 

p u b l i c : 

int operator<=(Point2 a) const 

{return (y <= a.y);} 

p r i v a t e : 

int p; // 数组X中相同点的索引 

float x, y; // 点坐标 

} ; 

所输入的n 个点可以用数组X来表示。假设X中的点已按照x 坐标排序，在分割过程中如果当前考察的点是X [l :r]，那么首先计算m= (l+r) / 2，X[ l:m]中的点属于A，剩下的点属于B。计算出A和B中的最近点对之后，还需要计算RA 和RB，然后确定是否存在更近的点对，其中一点属于RA，另一点属于RB。如果点已按y 坐标排序，那么可以用一种很简单的方式来测试图1 4 - 1 6。按y 坐标排序的点保存在另一个使用类P o i n t 2 (见程序14-8) 的数组中。注意到在P o i n t 2类中，为了便于y 坐标排序，已重载了操作符＜＝。成员p 用于指向X中的对应点。 

确定了必要的数据结构之后，再来看看所要产生的代码。首先定义一个模板函数d i s t (见程序1 4 - 9 )来计算点a, b 之间的距离。T可能是P o i n t 1或P o i n t 2，因此d i s t必须是P o i n t 1和P o i n t 2类的友元。 

程序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; 

} 

程序1 4 - 11 计算最近点对 

void close(Point1 X[], Point2 Y[], Point2 Z[], int l, int r, Point1& a, Point1& b, float& d) 

{//X[l:r] 按x坐标排序 

//Y[l:r] 按y坐标排序 

if (r-l == 1) {// 两个点 

a = X[l]; 

b = X[r]; 

d = dist(X[l], X[r]); 

r e t u r n ; } 

if (r-l == 2) {// 三个点 

// 计算所有点对之间的距离 

float d1 = dist(X[l], X[l+1]); 

float d2 = dist(X[l+1], X[r]); 

float d3 = dist(X[l], X[r]);


// 寻找最近点对 

if (d1 <= d2 && d1 <= d3) { 

a = X[l]; 

b = X[l+1]; 

d = d1; 

r e t u r n ; } 

if (d2 <= d3) {a = X[l+1]; 

b = X[r]; 

d = d2;} 

else {a = X[l]; 

b = X[r]; 

d = d3;} 

r e t u r n ; } 

/ /多于三个点，划分为两部分 

int m = (l+r)/2; // X[l:m] 在A中，余下的在B中 

// 在Z[l:m] 和Z [ m + 1 : r ]中创建按y排序的表 

int f = l, // Z[l:m]的游标 

g = m+1; // Z[m+1:r]的游标 

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

if (Y[i].p > m) Z[g++] = Y[i]; 

else Z[f++] = Y[i]; 

// 对以上两个部分进行求解 

c l o s e ( X , Z , Y, l , m , a , b , d ) ; 

float dr; 

Point1 ar, br; 

c l o s e ( X , Z , Y, m + 1 , r, a r, b r, d r ) ; 

// (a,b) 是两者中较近的点对 

if (dr < d) {a = ar; 

b = br; 

d = dr;} 

M e r g e ( Z , Y,l,m,r);// 重构Y 

/ /距离小于d的点放入Z 

int k = l; // Z的游标 

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

if (fabs(Y[m].x - Y[i].x) < d) Z[k++] = Y[i]; 

// 通过检查Z [ l : k - 1 ]中的所有点对，寻找较近的点对 

for (i = l; i < k; i++){ 

for (int j = i+1; j < k && Z[j].y - Z[i].y < d; 

j + + ) { 

float dp = dist(Z[i], Z[j]); 

if (dp < d) {// 较近的点对 

d = dp; 

a = X[Z[i].p]; 

b = X[Z[j].p];} 

} 

} 

}