最短点对

难点：如何测试。我的解决方式是：a,三种解法，看结果是否一致。b,小数据（100个点），人工排查。第一种方法，暴力法适合小数据。第二种方法：我的改进型。第三种方法：经典方法（分治法）。实验证明1000万数据时，我的算法有优势。
暴力算法，o(n2)。我的改进型要点：先对所有数据按y排序。只比较y距离小于等于已知最小距离的点对。经典方法：按y排序，分成两部分，递归调用。合并师只比较距离分界线不超过已知最小距离的点对。
实际证明500万数据以下，我的改进算法明显优于经典算法；1000万数据时，略强于经典算法。

 

核心代码：

double dis(const cpt& pt1,const cpt& pt2)
{
    return sqrt((double) (pt1.x-pt2.x)*(pt1.x-pt2.x)+(pt1.y-pt2.y)*(pt1.y-pt2.y)+(pt1.z-pt2.z)*(pt1.z-pt2.z) );
}

void initdata(cpt* pts,int inum)
{
    srand(time(null));

    for( int i = 0 ; i < inum ; i++)
    {
        pts[i].x = rand()%10000;
        pts[i].y = rand()%10000;
        pts[i].z = rand()%10000;
    }
}

double fun1(cpt* pts,const int inum)
{
     double dmindis = 10000*10000 ;
    for(int i = 0 ; i < inum ; i++ )
        for( int j = i+1 ; j < inum ; j++ )
        {
            const double d = dis(pts[i] , pts[j]);
            if( d < dmindis)
            {
                dmindis = d ;
            }
        }
        return dmindis;
}

class ccmpy
{
public:
    bool operator()(const cpt& pt1,const cpt& pt2)
    {
        return pt1.y < pt2.y ;
    }
};

double fun2(cpt* pts,const int inum)
{
    std::sort(pts,pts+inum,ccmpy() );

    double dmindis = 10000*10000 ;
    for(int i = 0 ; i < inum ; i++ )
        for( int j = i+1 ; j < inum ; j++ )
        {
            const double d = dis(pts[i] , pts[j]);
            if( d < dmindis)
            {
                dmindis = d ;
            }
            if( abs(pts[i].y - pts[j].y )> dmindis )
            {
                break;
            }
        }
        return dmindis;
}

double fun3(cpt* pts,const int inum)
{
    std::sort(pts,pts+inum,ccmpy() );

    if( inum < 100 )
    {
        return fun1(pts,inum);
    }

    const int imid = inum/2 ;
    const double dmin1 = fun3(pts,imid);
    const double dmin2 = fun3(pts+imid,inum-imid);
    double dmindis = min(dmin1,dmin2) ;
    for(int i = imid-1 ; i >= 0 ; i-- )//左集合
    {
        if( abs(pts[i].y - pts[imid].y ) > dmindis )
        {
            break;
        }
        for( int j = imid ; j < inum ; j++ )//右集合
        {
            const double d = dis(pts[i] , pts[j]);
            if( d < dmindis)
            {
                dmindis = d ;
            }
            if( abs(pts[i].y - pts[j].y )> dmindis )
            {
                break;
            }
        }
    }
        return dmindis;
}

 

可通过以下链接下载测试数据，exe，源码(vs2005,vc8)
https://pan.baidu.com/s/1qyqgtuvqtuh3n7tclhxkta