在一个集合中有n个点,找出这n个点中最短的两个点的位置,并输出这个位置:
#include <iostream> #include <cmath> using namespace std; class PointX{ public: double x; double y; }; class PointY{ public: double x; double y; int p; }; //考虑使用运算符重载,与类内部写一个比较函数功能相似 void sortPointX(PointX X[],int len){ PointX temp; for(int i=len;i>0;--i){//有len个元素进行len-1次比较 for(int j=0;j<i-1;++j){ if(X[j].x>X[j+1].x){ temp = X[j+1]; X[j+1]=X[j]; X[j]=temp; } } } } void sortPointY(PointY Y[],int len){ PointY temp; for(int i=len;i>0;--i){//表示有多少个元素进行比较 for(int j=0;j<i-1;++j){ if(Y[j].y>Y[j+1].y){ temp = Y[j+1]; Y[j+1]=Y[j]; Y[j]=temp; } } } } //两点之间的距离 template <class Type> inline double dist(const Type& u, const Type& v){ double dx=u.x-v.x; double dy=u.y-v.y; return sqrt(dx*dx+dy*dy); } void mergeY(PointY Z[],PointY Y[],int l,int m,int r){ int i=l; int j=m+1; int k=l; while(i<=m-1&&j<=r) { if(Z[i].y<Z[j].y){ Y[k++]=Z[i++]; }else{ Y[k++]=Z[j++]; } } while(i<=m-1){ Y[k++]=Z[i++]; } while(j<=r){ Y[k++]=Z[j++]; } } //求最短距离 void closest(PointX X[],PointY Y[],PointY Z[],int l,int r,PointX &a,PointX& b,double& d){ cout<<l<<" "<<r<<endl; cout<<"hello closest"<<endl; if(r<l){ cout<<"l:"<<l<<" r: "<<r<<endl; return; } if(r-l==0)return; if(r-l==1){ a=X[l]; b=X[r]; d=dist(a,b); return; } if(r-l==2){ double d1=dist(X[l],X[l+1]); double d2=dist(X[l+1],X[r]); double 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=dist(X[l+1],X[r]); }else{ a=X[l]; b=X[r]; d=dist(X[l],X[r]); } return; } //多于三点的情形,分治法 int mid = (l+r)/2; int f=l; int g=mid+1; for(int i=l;i<=r;++i){ if(Y[i].p>mid){ Z[g++]=Y[i]; } else { Z[f++]=Y[i]; } } closest(X,Z,Y,l,mid,a,b,d); double dr; PointX ar; PointX br; closest(X,Z,Y,mid+1,r,ar,br,dr); if(dr<d){ a=ar; b=br; d=dr; } // for(int i=l;i<=r;++i) // { // cout<<i<<" "<<Y[i].x<<" "<<Y[i].y<<endl; // } //重构数组Y mergeY(Z,Y,l,mid,r);//我不懂为什么要重构数组Y //把符合条件的点放到Z中 int k=l; for(int i=l;i<=r;++i){ if(fabs(Y[i].x-Y[mid].x)<d){ Z[k++]=Y[i]; } } //搜索Z[1:k-1] for(int i=l;i<k;++i){ for(int j=i+1;j<k&&(Z[j].y-Z[i].y)<d;++j){ double tem = dist(Z[j],Z[i]); if(tem<d){ a=X[Z[i].p]; cout<<a.x<<" () "<<a.y<<endl; cout<<Z[i].x<<" () "<<Z[i].y<<endl; b=X[Z[j].p]; d=tem; } } } } int main() { // void sortPointX(PointX X[],int len); // void sortPointY(PointY Y[],int len); // void closest(PointX X[],PointY Y[],PointY Z[],int a,int b,double d); cout << "Hello world!" << endl; time_t ti = time(NULL); cout<<ti<<endl; freopen("aaa.txt","r",stdin); PointX a,b; double d; PointX X[101]; PointY Y[101]; PointY Z[101]; int len; cin>>len; for(int i = 0;i<len;++i){ cin>>X[i].x>>X[i].y; } sortPointX(X,len); for(int i=0;i<len;++i){ Y[i].x=X[i].x; Y[i].y=X[i].y; Y[i].p=i; } sortPointY(Y,len); closest(X,Y,Z,0,len-1,a,b,d); cout<<"("<<a.x<<","<<a.y<<")"<<endl; cout<<"("<<b.x<<","<<b.y<<")"<<endl; cout<<"d: "<<d<<endl; time_t endTime=time(NULL); cout<<"所用时间:"<<endTime-ti<<endl; return 0; }
在aaa.txt中为测试的数据,可以随便写的:
10
1 3
2 4
3 5
4 3
5 9
6 8
7 7
10 6
11 6
13 8
运行结果: