通过代码来学习实例，看下面的代码：
//点结构
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作归并排序
void Merge(char sign ,Pair SR[] ,Pair TR[] ,long i ,long m ,long n)
{ // 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]
//int j,k,l;
for(int j=m+1,k=i;i<=m&&j<=n;++k) // 将SR中记录由小到大地并入TR
{
if(sign=='x')
{
if ( SR[i].x < SR[j].x )
TR[k]=SR[i++];
else
TR[k]=SR[j++];
}
else
{
if ( SR[i].y < SR[j].y )
TR[k]=SR[i++];
else
TR[k]=SR[j++];
}
}
if(i<=m)
{
for(int l=0;l<=mi;l++)
{
TR[k+l]=SR[i+l]; // 将剩余的SR[i..m]复制到TR
}
}
else
{
for(int l=0;l<=nj;l++)
{
TR[k+l]=SR[j+l]; // 将剩余的SR[j..n]复制到TR
}
}
}
void MSort(char sign ,Pair SR[] ,Pair TR1[] ,long s , long t)
{ // 将SR[s..t]归并排序为TR1[s..t].
if(s==t)
{
TR1[s] = SR[s];
}
else
{
//int m ;
int length = ts+1 ;//
Pair* TR2 = new Pair[points.pair_nums];
long m = (s+t)/2; // 将SR[s..t]平分为SR[s..m]和SR[m+1..t]
MSort(sign ,SR,TR2,s,m) ; // 递归地将SR[s..m]归并为有序的TR2[s..m]
MSort(sign ,SR,TR2,m+1,t) ; // 递归地将SR[m+1..t]归并为有序的TR2[m+1..t]
Merge(sign ,TR2,TR1,s,m,t) ; // 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]
delete[] TR2 ;
}
// cout << " Hello " ;
}
void Comp_CP(const Points& points ,Closest_Pair& closest_pair ,int mid ,int mid_value)
{
int i , j ;
int distance = sqrt( closest_pair.distance ) ;
i = mid ;
while( i >= 0 && points.p_pair[i].x > (mid_valuedistance) )
{
j = mid ;
while( points.p_pair[++j].x < (mid_value+distance) && j < points.pair_nums )
{
if( points.p_pair[j].y > (points.p_pair[i].y+distance) ||
points.p_pair[j].y < (points.p_pair[i].ydistance) )
//判断在y轴是否出界
continue ;
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 ;
cout << "Comp_CP: " << closest_pair.distance << endl ;
}
}
i ;
}
}
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 ;
}
void main()
{
time_t t;
srand((unsigned) time(&t));
char c ;
do
{
system("cls") ;
cout << "\n\n 请输入你要随机产生点对的对数： " ;
cin >> points.pair_nums ;
points.p_pair = new Pair[points.pair_nums] ;
for(int i=0 ;i<points.pair_nums ;++i)
{
points.p_pair[i].x= rand()%101 ;
points.p_pair[i].y= rand()%101 ;
}
