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 ;
}
//分治法求解，先排序
MSort('x' ,points.p_pair ,points.p_pair ,0 ,points.pair_nums1 ) ;
//蛮力法求解
closest_pair.distance = 32676 ;//MAX_SIZE
Brute_Force(points ,closest_pair ,0 ,points.pair_nums1 ) ;
closest_pair.distance = sqrt( closest_pair.distance ) ;
Print_Points( cout , points ,closest_pair ) ;
//分治法求解，先排序
//MSort('x' ,points.p_pair ,points.p_pair ,0 ,points.pair_nums1 ) ;
//分治法求解
closest_pair.distance = 32676 ;//MAX_SIZE
Divide_and_Conquer(points ,closest_pair ,0 ,points.pair_nums1 ) ;
closest_pair.distance = sqrt( closest_pair.distance ) ;
Print_Points( cout , points ,closest_pair ) ;
//MSort('x' ,points.p_pair ,points.p_pair ,0 ,points.pair_nums1 ) ;
// Print_Points( cout , points ,closest_pair ) ;
cout << "\n\n !!!按任意键继续，Esc退出程序!!!" << endl ;
}while( (c=getch())!=27 ) ;
return ;
}
3COME考试频道为您精心整理，希望对您有所帮助，更多信息在http://www.reader8.net/exam/
