最短點對

                                                                          ​​軟體架構師何志丹​​

難點：如何測試。我的解決方式是：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;
}