最近点对:最近点对问题疯狂代码！

通过代码来学习例子

看下面

代码:

//点结构

typedef struct Pair

{

x ;

y ;

} Pair ;

//最近点对结构

typedef struct Closest_Pair

{

Pair pair_a ,pair_b ;

double distance ;

} Closest_Pair ;

//点对结构

typedef struct Po

s

{

Pair* p_pair ;

pair_nums ;//点对数目

} Po

s

//蛮力法:分别计算每

对点的间

距离

然后找距离最小

那

对

bool Brute_Force(const Po

s& po

s ,Closest_Pair& closest_pair ,

from ,

to)

{

for(

i=from ;i<=to ;

i)

{

for(

j=i+1;j<=to ;

j)

{

double next= Account_Distance_2(po

s.p_pair[i] ,po

s.p_pair[j]) ;

(closest_pair.distance > next )

{

closest_pair.pair_a = po

s.p_pair[i] ;

closest_pair.pair_b = po

s.p_pair[j] ;

closest_pair.distance = next ;

}

}

}

true ;

}

//分治法:遵循分治思路方法

利用递归求出左子集和右子集

最近点对

然后再对两子集的间点对进

步分析比较

最后求出整个点集最近点对

void Divide_and_Conquer(const Po

s& po

s ,Closest_Pair& closest_pair ,

from ,

to)

{

( (to-from+1) <4 )

{

Brute_Force(po

s ,closest_pair ,from ,to ) ;

cout << "<4 " << closest_pair.distance << endl ;

//system("pause") ;

}

{

mid = (from+to)/2 ;

mid_value = po

s.p_pair[mid].x ;

Divide_and_Conquer(po

s ,closest_pair ,from ,mid) ;

Divide_and_Conquer(po

s ,closest_pair ,mid+1 ,to) ;

Comp_CP(po

s ,closest_pair ,mid ,mid_value) ;

}

;

}

#

"Head.h"

//---------------------------------------------------------------------------

typedef

RedType ;

typedef struct Pair

{

x ;

y ;

} Pair ;

typedef struct Closest_Pair

{

Pair pair_a ,pair_b ;

double distance ;

} Closest_Pair ;

typedef struct Po

s

{

Pair* p_pair ;

pair_nums ;//点对数目

} Po

s ;

//---------------------------------------------------------------------------

Po

s po

s ;

Closest_Pair closest_pair ;

//

pair_nums ;

//---------------------------------------------------------------------------

double Account_Distance_2(const Pair& A ,const Pair& B )

{

( (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y) ) ;

}

//---------------------------------------------------------------------------

void Pr

_Po

s(ostream& outs ,const Po

s& po

s ,const Closest_Pair& closest_pair )

{

outs << "\n\n\n 随机产生点对如下:\n" ;

for(

i=0 ;i<po

s.pair_nums ;

i)

{

outs << " (" << po

s.p_pair[i].x << " , " << po

s.p_pair[i].y << " ) " ;

((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 Po

s& po

s ,Closest_Pair& closest_pair ,

from ,

to)

{

for(

i=from ;i<=to ;

i)

{

for(

j=i+1;j<=to ;

j)

{

double next = Account_Distance_2(po

s.p_pair[i] ,po

s.p_pair[j]) ;//sqrt( )

(closest_pair.distance > next )

{

closest_pair.pair_a = po

s.p_pair[i] ;

closest_pair.pair_b = po

s.p_pair[j] ;

closest_pair.distance = next ;

}

}

}

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]

//

j,k,l;

for(

j=m+1,k=i;i<=m&&j<=n;

k) // 将SR中记录由小到大地并入TR

{

(sign

'x')

{

( SR[i].x < SR[j].x )

TR[k]=SR[i

];

TR[k]=SR[j

];

}

{

( SR[i].y < SR[j].y )

TR[k]=SR[i

];

TR[k]=SR[j

];

}

}

(i<=m)

{

for(

l=0;l<=m-i;l

)

{

TR[k+l]=SR[i+l]; // 将剩余

SR[i..m]复制到TR

}

}

{

for(

l=0;l<=n-j;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].

t)

{

TR1[s] = SR[s];

}

{

//

m ;

length = t-s+1 ;//

Pair* TR2 =

Pair[po

s.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 Po

s& po

s ,Closest_Pair& closest_pair ,

mid ,

mid_value)

{

i , j ;

distance = sqrt( closest_pair.distance ) ;

i = mid ;

while( i >= 0 && po

s.p_pair[i].x > (mid_value-distance) )

{

j = mid ;

while( po

s.p_pair[

j].x < (mid_value+distance) && j < po

s.pair_nums )

{

( po

s.p_pair[j].y > (po

s.p_pair[i].y+distance) ||

po

s.p_pair[j].y < (po

s.p_pair[i].y-distance) )

//判断在y轴是否出界

continue ;

double next = Account_Distance_2( po

s.p_pair[i] ,po

s.p_pair[j]);//sqrt( )

(closest_pair.distance > next )

{

closest_pair.pair_a = po

s.p_pair[i] ;

closest_pair.pair_b = po

s.p_pair[j] ;

closest_pair.distance = next ;

cout << "Comp_CP: " << closest_pair.distance << endl ;

}

}

i-- ;

}

}

//---------------------------------------------------------------------------

void Divide_and_Conquer(const Po

s& po

s ,Closest_Pair& closest_pair ,

from ,

to)

{

( (to-from+1) <4 )

{

Brute_Force(po

s ,closest_pair ,from ,to ) ;

cout << "<4 " << closest_pair.distance << endl ;

//system("pause") ;

}

{

mid = (from+to)/2 ;

mid_value = po

s.p_pair[mid].x ;

Divide_and_Conquer(po

s ,closest_pair ,from ,mid) ;

Divide_and_Conquer(po

s ,closest_pair ,mid+1 ,to) ;

Comp_CP(po

s ,closest_pair ,mid ,mid_value) ;

}

;

}

//---------------------------------------------------------------------------

void

{

time_t t;

srand((unsigned) time(&t));

char c ;

do

{

system("cls") ;

cout << "\n\n 请输入你要随机产生点对

对数: " ;

cin >> po

s.pair_nums ;

po

s.p_pair =

Pair[po

s.pair_nums] ;

for(

i=0 ;i<po

s.pair_nums ;

i)

{

po

s.p_pair[i].x= rand

%101 ;

po

s.p_pair[i].y= rand

%101 ;

}

//分治法求解

先排序

MSort('x' ,po

s.p_pair ,po

s.p_pair ,0 ,po

s.pair_nums-1 ) ;

/*//

*/

//蛮力法求解

closest_pair.distance = 32676 ;//MAX_SIZE

Brute_Force(po

s ,closest_pair ,0 ,po

s.pair_nums-1 ) ;

closest_pair.distance = sqrt( closest_pair.distance ) ;

Pr

_Po

s( cout , po

s ,closest_pair ) ;

//分治法求解

先排序

//MSort('x' ,po

s.p_pair ,po

s.p_pair ,0 ,po

s.pair_nums-1 ) ;

//分治法求解

closest_pair.distance = 32676 ;//MAX_SIZE

Divide_and_Conquer(po

s ,closest_pair ,0 ,po

s.pair_nums-1 ) ;

closest_pair.distance = sqrt( closest_pair.distance ) ;

Pr

_Po

s( cout , po

s ,closest_pair ) ;

//MSort('x' ,po

s.p_pair ,po

s.p_pair ,0 ,po

s.pair_nums-1 ) ;

// Pr

_Po

s( cout , po

s ,closest_pair ) ;

cout << "\n\n !!!按任意键继续

Esc退出

!!!" << endl ;

}while( (c=getch

)!=27 ) ;

;

}

//---------------------------------------------------------------------------

#

"Head.h"
//---------------------------------------------------------------------------
typedef

RedType ;
typedef struct Pair
{

x ;

y ;
} Pair ;
typedef struct Closest_Pair
{
Pair pair_a ,pair_b ;
double distance ;
} Closest_Pair ;
typedef struct Po

s
{
Pair* p_pair ;

pair_nums ;//点对数目
} Po

s ;
//---------------------------------------------------------------------------

Po

s po

s ;
Closest_Pair closest_pair ;
//

pair_nums ;
//---------------------------------------------------------------------------
double Account_Distance_2(const Pair& A ,const Pair& B )
{

( (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y) ) ;
}
//---------------------------------------------------------------------------
void Pr

_Po

s(ostream& outs ,const Po

s& po

s ,const Closest_Pair& closest_pair )
{
outs << "\n\n\n 随机产生点对如下:\n" ;
for(

i=0 ;i<po

s.pair_nums ;

i)
{
outs << " (" << po

s.p_pair[i].x << " , " << po

s.p_pair[i].y << " ) " ;

((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 Po

s& po

s ,Closest_Pair& closest_pair ,

from ,

to)
{
for(

i=from ;i<=to ;

i)
{
for(

j=i+1;j<=to ;

j)
{
double next = Account_Distance_2(po

s.p_pair[i] ,po

s.p_pair[j]) ;//sqrt( )

(closest_pair.distance > next )
{
closest_pair.pair_a = po

s.p_pair[i] ;
closest_pair.pair_b = po

s.p_pair[j] ;
closest_pair.distance = next ;
}
}
}

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]
//

j,k,l;
for(

j=m+1,k=i;i<=m&&j<=n;

k) // 将SR中记录由小到大地并入TR
{

(sign

'x')
{

( SR[i].x < SR[j].x )
TR[k]=SR[i

];

TR[k]=SR[j

];
}

{

( SR[i].y < SR[j].y )
TR[k]=SR[i

];

TR[k]=SR[j

];
}
}

(i<=m)
{
for(

l=0;l<=m-i;l

)
{
TR[k+l]=SR[i+l]; // 将剩余

SR[i..m]复制到TR
}
}

{
for(

l=0;l<=n-j;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].

t)
{
TR1[s] = SR[s];
}

{
//

m ;

length = t-s+1 ;//
Pair* TR2 =

Pair[po

s.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 Po

s& po

s ,Closest_Pair& closest_pair ,

mid ,

mid_value)
{

i , j ;

distance = sqrt( closest_pair.distance ) ;
i = mid ;
while( i >= 0 && po

s.p_pair[i].x > (mid_value-distance) )
{
j = mid ;
while( po

s.p_pair[

j].x < (mid_value+distance) && j < po

s.pair_nums )
{

( po

s.p_pair[j].y > (po

s.p_pair[i].y+distance) ||
po

s.p_pair[j].y < (po

s.p_pair[i].y-distance) )
//判断在y轴是否出界
continue ;
double next = Account_Distance_2( po

s.p_pair[i] ,po

s.p_pair[j]);//sqrt( )

(closest_pair.distance > next )
{
closest_pair.pair_a = po

s.p_pair[i] ;
closest_pair.pair_b = po

s.p_pair[j] ;
closest_pair.distance = next ;
cout << "Comp_CP: " << closest_pair.distance << endl ;
}

}
i-- ;
}
}
//---------------------------------------------------------------------------
void Divide_and_Conquer(const Po

s& po

s ,Closest_Pair& closest_pair ,

from ,

to)
{

( (to-from+1) <4 )
{
Brute_Force(po

s ,closest_pair ,from ,to ) ;
cout << "<4 " << closest_pair.distance << endl ;
//system("pause") ;
}

{

mid = (from+to)/2 ;

mid_value = po

s.p_pair[mid].x ;

Divide_and_Conquer(po

s ,closest_pair ,from ,mid) ;
Divide_and_Conquer(po

s ,closest_pair ,mid+1 ,to) ;
Comp_CP(po

s ,closest_pair ,mid ,mid_value) ;
}

;
}
//---------------------------------------------------------------------------
void

{
time_t t;
srand((unsigned) time(&t));
char c ;
do
{
system("cls") ;

cout << "\n\n 请输入你要随机产生点对

对数: " ;
cin >> po

s.pair_nums ;
po

s.p_pair =

Pair[po

s.pair_nums] ;

for(

i=0 ;i<po

s.pair_nums ;

i)
{
po

s.p_pair[i].x= rand

%101 ;
po

s.p_pair[i].y= rand

%101 ;
}
//分治法求解

先排序
MSort('x' ,po

s.p_pair ,po

s.p_pair ,0 ,po

s.pair_nums-1 ) ;
/*//
*/
//蛮力法求解
closest_pair.distance = 32676 ;//MAX_SIZE
Brute_Force(po

s ,closest_pair ,0 ,po

s.pair_nums-1 ) ;
closest_pair.distance = sqrt( closest_pair.distance ) ;
Pr

_Po

s( cout , po

s ,closest_pair ) ;

//分治法求解

先排序
//MSort('x' ,po

s.p_pair ,po

s.p_pair ,0 ,po

s.pair_nums-1 ) ;

//分治法求解
closest_pair.distance = 32676 ;//MAX_SIZE
Divide_and_Conquer(po

s ,closest_pair ,0 ,po

s.pair_nums-1 ) ;
closest_pair.distance = sqrt( closest_pair.distance ) ;
Pr

_Po

s( cout , po

s ,closest_pair ) ;

//MSort('x' ,po

s.p_pair ,po

s.p_pair ,0 ,po

s.pair_nums-1 ) ;

// Pr

_Po

s( cout , po

s ,closest_pair ) ;

cout << "\n\n !!!按任意键继续

Esc退出

!!!" << endl ;

}while( (c=getch

)!=27 ) ;

;
}
//---------------------------------------------------------------------------

Tags:

最近点对:最近点对问题

延伸阅读

最新评论

发表评论

赞助商广告

随机更新

热门标注

最近更新

最新标注