到现在看着伪代码写不出来递归函数，不知道计算过程应该放在哪儿，我觉得是够菜了，一个一维的求解弄一晚上。
菜的真实，菜的绝望。
#include<stdio.h> #include<stdlib.h> #include<math.h> class pair{ public: double dis; int point1,point2; operator<(const pair &p) { return dis<p.dis; } }; void Swap(double *a,double *b) { double tep=*a; *a=*b; *b=tep; } int Partition(double *a,int l,int r,double value) { double tep=value; int i=l,j=r; while(i<j) { while(a[i]<tep && i<r) i++; while(a[j]>tep && j>l) j--; if(i<j) Swap(a+i,a+j); } return j; } void quicksort(double *a,int l,int r) { if(l>=r) return ; int select=rand()%(r-l+1)+l; double tep=a[select]; int j=Partition(a,l,r,tep); quicksort(a,l,j); quicksort(a,j+1,r); } double Select(double *a,int l,int r,int rank) { if(r-l+1<=75) { quicksort(a,l,r); return a[l+rank-1]; } for(int i=0;i<=(r-l-4)/5;i++) { quicksort(a,l+i*5,l+5*i+4); Swap(a+l+5*i+2,a+l+i); } double mid=Select(a,l,l+(r-l-4)/5,(r-l-4)/10); int index=Partition(a,l,r,mid); int surplus=index-l+1; if(surplus>=rank) return Select(a,l,index,rank); else return Select(a,index+1,r,surplus-rank); } int MAX(double *a,int l,int r) { double m=-1e7; int f=0; for(int i=l;i<=r;i++) if(m<a[i]) m=a[i],f=i; return f; } double MIN(double *a,int l,int r) { double m=1e7,f=0; for(int i=l;i<=r;i++) if(m>a[i]) m=a[i],f=i; return f; } pair cloest(double *a,int l,int r) { pair ans={1e7,l,r}; if(r-l<1) return ans; double mid=Select(a,l,r,(r-l+1)/2); int index=Partition(a,l,r,mid); pair dis1=cloest(a,l,index),dis2=cloest(a,index+1,r); int Max=MAX(a,l,index); int Min=MIN(a,index+1,r); double t=a[Min]-a[Max]; pair tt={t,Max,Min}; if(dis1.dis<dis2.dis) { if(dis1.dis<tt.dis) ans=dis1; else ans=tt; } else { if(tt.dis<dis2.dis) ans=tt; else ans=dis2; } return ans; } int main() { int n; double p[10005]; pair dis; printf("Please input the number of points\n"); scanf("%d",&n); for(int i=0;i<n;i++) scanf("%lf",&p[i]); dis=cloest(p,0,n-1); printf("%.3lf p1:%d p2:%d\n",dis.dis,dis.point1,dis.point2); return 0; }二维的明天补上
#include<bits/stdc++.h> using namespace std; class PointX{ public: int no; double x,y; int operator<(const PointX &p) { return x<p.x; } int operator>(const PointX &p) { return x>p.x; } }; class PointY{ public: int no_X; double x,y; int operator<(const PointY &p) { return y<p.y; } int operator>(const PointY &p) { return y>p.y; } }; template<typename T> void Merge(T a[],T b[],int l,int mid,int r)//give a to b { int i=l,j=mid+1; int st=l; while(i<=mid && j<=r) { if(a[i]<a[j]) b[st++]=a[i++]; else b[st++]=a[j++]; } while(i<=mid) b[st++]=a[i++]; while(j<=r) b[st++]=a[j++]; } template<typename T> void Swap(T *a,T *b) { T temp=*a; *a=*b; *b=temp; } template<typename T> void quicksort(T *a,int l,int r) { if(l>=r) return ; int i=l,j=r; int select=rand()%(r-l+1)+l; T v=a[select]; while(1) { while(a[i]<v && i<r) i++; while(a[j]>v && j>l) j--; if(i>=j) break; Swap(a+i,a+j); } quicksort(a,l,j); quicksort(a,j+1,r); } template<typename T> double Distance(T a,T b) { double xx=a.x-b.x; double yy=a.y-b.y; return sqrt(xx*xx+yy*yy); } void closest(PointX *x,PointY *y,PointY *z,int l,int r,PointX &ans1,PointX &ans2,double &dis) { if(r-l==1) { ans1=x[l]; ans2=x[r]; dis=Distance(x[l],x[r]); return ; } if(r-l==2) { double dis1=Distance(x[l],x[l+1]);//l,l+1 double dis2=Distance(x[l],x[r]);//l,r double dis3=Distance(x[l+1],x[r]);//l+1,r if(dis1>dis2){ if(dis1>dis3) {ans1=x[l]; ans2=x[l+1]; dis=dis1;} else {ans1=x[l+1];ans2=x[r];dis=dis3;} } else{ if(dis2>dis3){ans1=x[l];ans2=x[r];dis=dis2;} else{ans1=x[l+1];ans2=x[r];dis=dis3;}; } return ; } int mid=(l+r)/2; int s=l,t=mid+1; for(int i=l;i<=r;i++) { if(y[i].no_X>mid) z[t++]=y[i]; else z[s++]=y[i]; } closest(x,z,y,l,mid,ans1,ans2,dis); double an; PointX xx,yy; closest(x,z,y,mid+1,r,xx,yy,an); Merge(z,y,l,mid,r); if(an>dis){ dis=an; ans1=xx; ans2=yy; } int st=l; for(int i=l;i<=r;i++) { if(fabs(y[i].x-x[mid].x)<dis) z[st++]=y[i]; } for(int i=l;i<st;i++) { for(int j=i+1;j<st && z[j].y-z[i].y<dis;j++) { double tep=Distance(z[i],z[j]); if(tep<dis) { dis=tep; ans1=x[z[i].no_X];ans2=x[z[j].no_X]; } } } } void calculate(PointX *x,int n,PointX &ans1,PointX &ans2,double &dis) { if(n<2) return ; quicksort(x,0,n-1); PointY *y=new PointY[n]; for(int i=0;i<n;i++) { y[i].no_X=i; y[i].x=x[i].x; y[i].y=x[i].y; } quicksort(y,0,n-1); PointY *z=new PointY[n]; closest(x,y,z,0,n-1,ans1,ans2,dis); delete y; delete z; } int main() { int n; PointX x[1000]; scanf("%d",&n); for(int i=0;i<n;i++) { x[i].no=i; scanf("%lf%lf",&x[i].x,&x[i].y); } PointX ans1,ans2; double dis; calculate(x,n,ans1,ans2,dis); printf("The smallest Distance is %lf\n",dis); printf("The first point's coordinate: x:%lf y:%lf\n",ans1.x,ans1.y); printf("The second point's coordinate: x:%lf y:%lf\n",ans2.x,ans2.y); return 0; }基本是按书上的做法来的，就是写起来有点复杂啊，自己实现又写不出来，只能看看博客讨讨生活。
