最接近点对问题修改

《最接近点对问题修改》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、//11.cpp:定¡§义°?控?制?台¬¡§应®

2、用®?程¨¬序¨°的Ì?入¨?口¨²点Ì?。¡ê//#include"stdafx.h"#include#include//usingnamespacestd;//#defineN4;classPointX{public:intoperator<=(PointXa)const{return(x<=a.x);};floatx,y;intID;};classPointY{public:intoperator<=(PointYa)const{return(y<

3、=a.y);};intp;floatx,y;};templatevoidMergePass(Typex[],Typey[],ints,intn){inti=0;while(i<=n-2*s){Merge(x,y,i,i+s-1,i+2*s-1);i=i+2*s;}if(i+sinlinefloatdistance(constType&u,constType&

4、v){floatdx=u.x-v.x;floatdy=u.y-v.y;returnsqrt(dx*dx+dy*dy);}templatevoidMergeSort(Typea[],intn){Type*b=newType[n];ints=1;while(svoidMerge(Typec[],Typed[],intl,intm,intr){inti=l,j=m+1,k=l;wh

5、ile((i<=m)&&(j<=r))if(c[i]<=c[j])d[k++]=c[i++];elsed[k++]=c[j++];if(i>m)for(intq=j;q<=r;q++)d[k++]=c[q];elsefor(intq=i;q<=m;q++)d[k++]=c[q];}voidclosest(PointXX[],PointYY[],PointYZ[],intl,intr,PointX&a,PointX&b,float&d){if(r-l==1){a=X[l];b=X[r];d=distance(X[l],X[r]);return

6、;}if(r-l==2){floatd1=distance(X[l],X[l+1]);floatd2=distance(X[l+1],X[r]);floatd3=distance(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;}intm=(l+r)/2;intf=l,g=m+1;for(inti=l;i<=r;i++){if(Y[i].p>m

7、)Z[g++]=Y[i];elseZ[f++]=Y[i];}closest(X,Z,Y,l,m,a,b,d);floatdr;PointXar,br;closest(X,Z,Y,m+1,r,ar,br,dr);if(dr

8、atdp=distance(Z[i],Z[j]);if(dp

9、osest(X,Y,Z,0,n-1,a,b,d);delete[]Y;delete[]Z;returntrue;}int_tmain(intargc,_TCHAR*argv[])