ALG.rar_visual c

#include <stdio.h> #include <math.h> #define false 0 #define true 1 class PointX { public: int operator <= (PointX a)const {return x<=a.x;} // private: int ID;//点编号 float x,y; }; class PointY { public: int operator <= (PointY a)const {return y<=a.y;} // private: int p;//同一点在数组X中坐标 float x,y; }; template <class Type> inline float distance(const Type u,const Type v) { float dx=u.x-v.x; float dy=u.y-v.y; return sqrt(dx*dx+dy*dy); } template <class Type> void Merge(Type *c,Type *d,int l,int m,int r) {//合并c[l:m],c[m+1:r]到d[l,r] int i=l,j=m+1,k=l,q; while ((i<=m)&&(j<=r)) if (c[i]<=c[j])d[k++]=c[i++]; else d[k++]=c[j++]; if(i>m) for (q=j;q<=r;q++)d[k++]=c[q]; else for (q=i;q<=m;q++)d[k++]=c[q]; } template <class Type> void MergePass(Type *x,Type *y,int s,int n) {//合并长度为s的相邻子数组 int j,i=0; while (i<=n-2*s) { Merge(x,y,i,i+s-1,i+2*s-1); i=i+2*s; } //剩下元素个数少于2s if (i+s<n) Merge(x,y,i,i+s-1,n-1); else for(j=i;j<=n-1;j++)y[j]=x[j]; } template <class Type> void MergeSort(Type *a,int n) { Type *b=new Type[n]; int s=1; while (s<n) { MergePass(a,b,s,n); s+=s; MergePass(b,a,s,n); s+=s; } } void closest(PointX *X,PointY *Y,PointY *Z,int l,int r, PointX &a,PointX &b,float &d) { int i,j,k,m,f,g; float dr,dp,d1,d2,d3; PointX ar,br; if (r-l==1)//只有2点 { a=X[l]; b=X[r]; d=distance(X[l],X[r]); return; } if (r-l==2)//3点情况 { d1=distance(X[l],X[l+1]); d2=distance(X[l+1],X[r]); d3=distance(X[l],X[r]); if ((d1<=d2)&&(d1<=d3)) { a=X[l]; b=X[l+1]; d=d1; return; } if ((d2<=d1)&&(d2<=d3)) { a=X[l+1]; b=X[r]; d=d2; return; } if ((d3<=d2)&&(d3<=d1)) { a=X[l]; b=X[r]; d=d3; return; } } //多于3点 m=(l+r)/2; f=l; g=m+1; for(i=l;i<=r;i++) if (Y[i].p>m)Z[g++]=Y[i]; else Z[f++]=Y[i]; closest(X,Z,Y,l,m,a,b,d); closest(X,Z,Y,m+1,r,ar,br,dr); if (dr<d) { a=ar;b=br;d=dr; } Merge(Z,Y,l,m,r);//重构数组Y k=l; for (i=l;i<=r;i++) if (fabs(Y[m].x-Y[i].x)<d) Z[k++]=Y[i]; for (i=l;i<k;i++) for(j=i+1;(j<k)&&(Z[j].y-Z[i].y<d);j++) { dp=distance(Z[i],Z[j]); if (dp<d) { d=dp; a=X[Z[i].p]; b=X[Z[j].p]; } } } int Cpair2(PointX *X,int n,PointX &a,PointX &b,float &d) { int i; PointY *Z,*Y; if(n<2)return false; MergeSort(X,n); Y=new PointY[n]; for(i=0;i<n;i++) { Y[i].p=i; Y[i].x=X[i].x; Y[i].y=X[i].y; } MergeSort(Y,n); Z=new PointY[n]; closest(X,Y,Z,0,n-1,a,b,d); delete []Y; delete []Z; return true; } void main(void) { PointX X[]={{1,0.3,0.5},{2,0.9,0.15},{3,0.4,0.1},{4,0.5,0.5}, {5,0.2,0.3},{6,0.2,0.2},{7,0.9,0.8},{8,0.85,0.2}}; PointX a,b; float d; int ok=false; ok=Cpair2(X,8,a,b,d); if (ok) printf("a=%d,b=%d,dist=%f\n",a.ID,b.ID,d); else printf("False!\n"); getchar(); }