通过代码来学习实例，看下面的代码：
//点结构
typedef struct Pair
{
int x ;
int y ;
} Pair ;
//最近点对结构
typedef struct Closest_Pair
{
Pair pair_a ,pair_b ;
double distance ;
} Closest_Pair ;
//点对结构
typedef struct Points
{
Pair* p_pair ;
int pair_nums ;//点对数目
} Points
//蛮力法：分别计算每一对点之间的距离，然后找距离最小的那一对
bool Brute_Force(const Points& points ,Closest_Pair& closest_pair ,int from ,int to)
{
for(int i=from ;i<=to ;++i)
{
for(int j=i+1;j<=to ;++j)
{
double next= Account_Distance_2(points.p_pair[i] ,points.p_pair[j]) ; if(closest_pair.distance > next )
{
closest_pair.pair_a = points.p_pair[i] ;
closest_pair.pair_b = points.p_pair[j] ;
closest_pair.distance = next ;
}
}
}
return true ;
}
//分治法：遵循分治方法，利用递归求出左子集和右子集的最近点对，然后再对两子集之间点对进一步分析比较，最后求出整个点集最近点对。
void Divide_and_Conquer(const Points& points ,Closest_Pair& closest_pair ,int from ,int to)
{
if( (tofrom+1) <4 )
{
Brute_Force(points ,closest_pair ,from ,to ) ;
cout << "<4 " << closest_pair.distance << endl ;
//system("pause") ;
}
else
{
int mid = (from+to)/2 ;
int mid_value = points.p_pair[mid].x ;
Divide_and_Conquer(points ,closest_pair ,from ,mid) ;
Divide_and_Conquer(points ,closest_pair ,mid+1 ,to) ;
Comp_CP(points ,closest_pair ,mid ,mid_value) ;
}
return ;
}
#include "Head.h"
typedef int RedType ;
typedef struct Pair
{
int x ;
int y ;
} Pair ;
typedef struct Closest_Pair
{
Pair pair_a ,pair_b ;
double distance ;
} Closest_Pair ;
typedef struct Points
{
Pair* p_pair ;
int pair_nums ;//点对数目
} Points ;
Points points ;
Closest_Pair closest_pair ;
//int pair_nums ;
double Account_Distance_2(const Pair& A ,const Pair& B )
{
return ( (A.xB.x)*(A.xB.x)+(A.yB.y)*(A.yB.y) ) ;
}
void Print_Points(ostream& outs ,const Points& points ,const Closest_Pair& closest_pair )
{
outs << "\n\n\n 随机产生点对如下：\n" ;
for(int i=0 ;i<points.pair_nums ;++i)
{
outs << " (" << points.p_pair[i].x << " , " << points.p_pair[i].y << " ) " ;
if((i+1)%5==0)
{
outs << endl ;
}
}
outs << "\n\n 由以上点对可得最近点对为： ( "
<< closest_pair.pair_a.x << " , " << closest_pair.pair_a.y << " ) ,( "
<< closest_pair.pair_b.x << " , " << closest_pair.pair_b.y << " ) " ;
outs << "\n 该点对距离为：" << closest_pair.distance << endl ;
}
bool Brute_Force(const Points& points ,Closest_Pair& closest_pair ,int from ,int to)
{
for(int i=from ;i<=to ;++i)
{
for(int j=i+1;j<=to ;++j)
{
double next = Account_Distance_2(points.p_pair[i] ,points.p_pair[j]) ;//sqrt( )
if(closest_pair.distance > next )
{
closest_pair.pair_a = points.p_pair[i] ;
closest_pair.pair_b = points.p_pair[j] ;
closest_pair.distance = next ;
}
}
}
return true ;
}
// 对顺序表L作归并排序。
