C++實(shí)例:最近點(diǎn)對問題

通過代碼來學(xué)習(xí)實(shí)例，看下面的代碼：
    //點(diǎn)結(jié)構(gòu)
    typedef struct Pair
    {
    int x ;
    int y ;
    } Pair ;
    //最近點(diǎn)對結(jié)構(gòu)
    typedef struct Closest_Pair
    {
    Pair pair_a ,pair_b ;
    double distance ;
    } Closest_Pair ;
    //點(diǎn)對結(jié)構(gòu)
    typedef struct Points
    {
    Pair* p_pair ;
    int pair_nums ;//點(diǎn)對數(shù)目
    } Points
    //蠻力法：分別計(jì)算每一對點(diǎn)之間的距離，然后找距離最小的那一對
    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 ;
    }
    //分治法：遵循分治方法，利用遞歸求出左子集和右子集的最近點(diǎn)對，然后再對兩子集之間點(diǎn)對進(jìn)一步分析比較，最后求出整個(gè)點(diǎn)集最近點(diǎn)對。
    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 ;//點(diǎn)對數(shù)目
    } 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 隨機(jī)產(chǎn)生點(diǎn)對如下：\n" ;
    for(int i=0 ;i    {
    outs << " (" << points.p_pair[i].x << " , " << points.p_pair[i].y << " ) " ;
    if((i+1)%5==0)
    {
    outs << endl ;
    }
    }
    outs << "\n\n 由以上點(diǎn)對可得最近點(diǎn)對為： ( "
    << closest_pair.pair_a.x << " , " << closest_pair.pair_a.y << " ) ,( "
    << closest_pair.pair_b.x << " , " << closest_pair.pair_b.y << " ) " ;
    outs << "\n 該點(diǎ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作歸并排序。通過代碼來學(xué)習(xí)實(shí)例，看下面的代碼：
    //點(diǎn)結(jié)構(gòu)
    typedef struct Pair
    {
    int x ;
    int y ;
    } Pair ;
    //最近點(diǎn)對結(jié)構(gòu)
    typedef struct Closest_Pair
    {
    Pair pair_a ,pair_b ;
    double distance ;
    } Closest_Pair ;
    //點(diǎn)對結(jié)構(gòu)
    typedef struct Points
    {
    Pair* p_pair ;
    int pair_nums ;//點(diǎn)對數(shù)目
    } Points
    //蠻力法：分別計(jì)算每一對點(diǎn)之間的距離，然后找距離最小的那一對
    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 ;
    }
    //分治法：遵循分治方法，利用遞歸求出左子集和右子集的最近點(diǎn)對，然后再對兩子集之間點(diǎn)對進(jìn)一步分析比較，最后求出整個(gè)點(diǎn)集最近點(diǎn)對。
    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 ;//點(diǎn)對數(shù)目
    } 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 隨機(jī)產(chǎn)生點(diǎn)對如下：\n" ;
    for(int i=0 ;i    {
    outs << " (" << points.p_pair[i].x << " , " << points.p_pair[i].y << " ) " ;
    if((i+1)%5==0)
    {
    outs << endl ;
    }
    }
    outs << "\n\n 由以上點(diǎn)對可得最近點(diǎn)對為： ( "
    << closest_pair.pair_a.x << " , " << closest_pair.pair_a.y << " ) ,( "
    << closest_pair.pair_b.x << " , " << closest_pair.pair_b.y << " ) " ;
    outs << "\n 該點(diǎ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作歸并排序?！oid 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]復(fù)制到TR
    }
    }
    else
    {
    for(int l=0;l<=nj;l++)
    {
    TR[k+l]=SR[j+l]; // 將剩余的SR[j..n]復(fù)制到TR
    }
    }
    }
    void MSort(char sign ,Pair SR[] ,Pair TR1[] ,long s , long t)
    { // 將SR[s..t]歸并排序?yàn)門R1[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 請輸入你要隨機(jī)產(chǎn)生點(diǎn)對的對數(shù)： " ;
    cin >> points.pair_nums ;
    points.p_pair = new Pair[points.pair_nums] ;
    for(int i=0 ;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 !!!按任意鍵繼續(xù)，Esc退出程序!!!" << endl ;
    }while( (c=getch())!=27 ) ;
    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 ;//點(diǎn)對數(shù)目
    } 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 隨機(jī)產(chǎn)生點(diǎn)對如下：\n" ;
    for(int i=0 ;i    {
    outs << " (" << points.p_pair[i].x << " , " << points.p_pair[i].y << " ) " ;
    if((i+1)%5==0)
    {
    outs << endl ;
    }
    }
    outs << "\n\n 由以上點(diǎn)對可得最近點(diǎn)對為： ( "
    << closest_pair.pair_a.x << " , " << closest_pair.pair_a.y << " ) ,( "
    << closest_pair.pair_b.x << " , " << closest_pair.pair_b.y << " ) " ;
    outs << "\n 該點(diǎ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]復(fù)制到TR
    }
    }
    else
    {
    for(int l=0;l<=nj;l++)
    {
    TR[k+l]=SR[j+l]; // 將剩余的SR[j..n]復(fù)制到TR
    }
    }
    }　void MSort(char sign ,Pair SR[] ,Pair TR1[] ,long s , long t)
    { // 將SR[s..t]歸并排序?yàn)門R1[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 請輸入你要隨機(jī)產(chǎn)生點(diǎn)對的對數(shù)： " ;
    cin >> points.pair_nums ;
    points.p_pair = new Pair[points.pair_nums] ;
    for(int i=0 ;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 !!!按任意鍵繼續(xù)，Esc退出程序!!!" << endl ;
    }while( (c=getch())!=27 ) ;
    return ;
     }