zuijindian.cpp

这是一个经典的寻找最近点对的算法实现

#include <math.h>
#include <iostream.h>
class Point2;
class Point1 {

friend float dist(const Point1&, const Point1&);

friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&, Point1&, float&);

friend bool closest(Point1 *, int, Point1&, Point1&,float&);

friend void main();

public :

int operator<=(Point1 a) const

{return (x <= a.x);}

private :

int ID; // 点的编号

float x, y; // 点坐标

} ;

class Point2 {

friend float dist(const Point2&, const Point2&);

friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&, Point1&, float&);

friend bool closest(Point1 *, int, Point1&, Point1&, float&);

friend void main();

public :

int operator<=(Point2 a) const

{return (y <= a.y);}

private :

int p; // 数组X中相同点的索引

float x, y; // 点坐标

} ;


template<class T>

void Merge(T c[], T d[], int l, int m, int r)

{// 把c[l:m]] 和c[m:r] 归并到d [ l : r ] .

int i=l, // 第一段的游标

j=m+1, // 第二段的游标

k=l; // 结果的游标

//只要在段中存在i和j，则不断进行归并

while((i<=m)&&(j<=r))

if(c[i]<=c[j]) d[k++]=c[i++];

else d[k++]=c[j++];

// 考虑余下的部分

if(i>m) for(int q=j;q<=r;q++)

d[k++]=c[q];

else for(int q=i;q<=m;q++)

d[k++]=c[q];

}



template<class T>

void MergePass(T x[], T y[], int s, int n)

{// 归并大小为s的相邻段

int i=0;

while (i<=n-2*s) {

// 归并两个大小为s的相邻段

Merge(x, y, i, i+s-1, i+2*s-1);

i=i+2*s;

}

// 剩下不足2个元素

if(i+s<n) Merge(x,y,i,i+s-1,n-1);

else for(int j=i;j<=n-1;j++)

// 把最后一段复制到y

y[j]=x[j];

}


template<class T>

void MergeSort(T a[], int n)

{// 使用归并排序算法对a[0:n-1] 进行排序

T *b=new T[n];

int s=1; // 段的大小

while(s<n) {

MergePass(a, b, s, n); // 从a归并到b

s+=s;

MergePass(b,a,s,n); // 从b 归并到a

s+=s;

}

}



template<class T>

inline float dist(const T& u, const T& v)

{ //计算点u 和v之间的距离

float dx=u.x-v.x ;

float dy = u.y-v. y ;

return float(sqrt(dx*dx+dy*dy));

}



bool closest(Point1 X[], int n, Point1& a, Point1& b, float& d)

{// 在n >= 2 个点中寻找最近点对

// 如果少于2个点，则返回f a l s e

// 否则，在a 和b中返回距离最近的两个点

if(n<2) return false;

// 按x坐标排序

MergeSort(X,n);

// 创建一个按y坐标排序的点数组

Point2 *Y = new Point2 [n];

for(int i=0;i<n;i++) {

// 将点i 从X 复制到Y

Y[i].p=i;

Y[i].x=X[i].x;

Y[i].y=X[i].y;

}

MergeSort(Y,n); // 按y坐标排序

// 创建临时数组

Point2 *Z=new Point2[n];

// 寻找最近点对

close(X,Y,Z,0,n-1,a,b,d) ;

// 删除数组并返回

delete []Y;

delete []Z;

return true;

}



void close(Point1 X[], Point2 Y[], Point2 Z[], int l, int r, Point1& a, Point1& b, float& d)

{//X[l:r] 按x坐标排序

//Y[l:r] 按y坐标排序

if(r-l==1) {// 两个点
a=X[l];

b=X[r];

d=dist(X[l],X[r]);

return ; }

if(r-l==2) {// 三个点

// 计算所有点对之间的距离

float d1=dist(X[l],X[l+1]);

float d2=dist(X[l+1],X[r]);

float d3=dist(X[l],X[r]);

// 寻找最近点对

if(d1<=d2&&d1<=d3) {

a=X[l];

b=X[l+1];

d=d1;

return ; }

if(d2<=d3) {a=X[l+1];

b=X[r];

d=d2;}

else {a=X[l];

b=X[r];

d=d3;}

return ; }

//多于三个点，划分为两部分

int m=(l+r)/2; // X[l:m] 在A中，余下的在B中

// 在Z[l:m] 和Z [ m + 1 : r ]中创建按y排序的表

int f=l, // Z[l:m]的游标

g=m+1; // Z[m+1:r]的游标

for (int i=l; i<=r;i++)

if(Y[i].p>m) Z[g++]=Y[i];

else Z[f++]=Y[i];

// 对以上两个部分进行求解

close(X,Z,Y,l,m,a,b,d) ;

float dr;

Point1 ar, br;

close(X,Z,Y,m+1,r,ar,br,dr) ;

// (a,b) 是两者中较近的点对

if(dr<d) {a=ar;

b=br;

d=dr;}

Merge(Z,Y,l,m,r);// 重构Y

//距离小于d的点放入Z

int k=l; // Z的游标

for (i=l; i<=r;i++)

if (float(fabs(Y[m].x-Y[i].x))<d) Z[k++]=Y[i];

// 通过检查Z [ l : k - 1 ]中的所有点对，寻找较近的点对

for(i=l;i<k;i++){

for (int j=i+1;j<k&&Z[j].y-Z[i].y<d;j++) 
{

float dp=dist(Z[i], Z[j]);

if(dp<d) {// 较近的点对

d=dp;

a=X[Z[i].p];

b=X[Z[j].p];}

}

}

}


void main()
{int i,n;
 Point1 X[100];
 Point1 a,b;
 float d;
 cout<<"请输入点的个数:";
 cin>>n;
 cout<<"请输入点的坐标:"<<endl;
 for(i=0;i<n;i++)
 {cin>>X[i].x>>X[i].y;
  //cout<<endl;
 }
 closest(X,n,a,b,d);
 cout<<"最近点对为:"<<"("<<a.x<<","<<a.y<<")"<<"("<<b.x<<","<<b.y<<")"<<endl;
 cout<<"最短距离为:"<<d;
}