nearestpoint.cpp

最接近点对问题是求二维坐标中的点对问题

#include<iostream.h>
#include<math.h>
#define N 4;
class PointX{
public:
	int operator <= (PointX a) const{
		return (x<=a.x);
	};
	float x,y;
	int ID;
private:
	
};
class PointY{
public:
	int operator <= (PointY a) const{
		return (y<=a.y);
	};
	int p;float x,y;
private:	
	
};
template<class Type>
void MergePass(Type x[],Type y[],int s,int n){
	int i=0;
	while(i<=n-2*s){
		Merge(x,y,i,i+s-1,i+2*s-1);
		i=i+2*s;
	}
	if(i+s<n)
		Merge(x,y,i,i+s-1,n-1);
	else for(int j=i;j<=n-1;j++)
		y[j]=x[j];
}
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 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;
	}
}
template<class Type>
void Merge(Type c[],Type d[],int l,int m,int r){
	int i=l,
		j=m+1,
		k=l;
	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];
}
void closest(PointX X[],PointY Y[],PointY Z[],int l,int r,PointX& a,PointX &b,float& d){
	if(r-l==1){
		a=X[l];
		b=X[r];
		d=distance(X[l],X[r]);
		return;
	}
	if(r-1==2){
		float d1=distance(X[l],X[l+1]);
		float d2=distance(X[l+1],X[r]);
		float d3=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;
	}
	int m=(l+r)/2;
	int f=l,g=m+1;
	for(int 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);
	float dr;
	PointX ar,br;
	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);
	int 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(int j=i+1;j<k&&Z[j].y-Z[i].y<d;j++){
			float dp=distance(Z[i],Z[j]);
			if(dp<d){
				d=dp;
				a=X[Z[i].p];
				b=X[Z[j].p];
			}
		}
	}
}
bool Cpair2(PointX X[],int n,PointX& a,PointX& b,float& d){
	if(n<2)return false;
	MergeSort(X,n);
	PointY *Y=new PointY[n];
	for(int i=0;i<n;i++){
		Y[i].p=i;
		Y[i].x=X[i].x;
		Y[i].y=X[i].y;
	}
	MergeSort(Y,n);
	PointY *Z=new PointY[n];
	closest(X,Y,Z,0,n-1,a,b,d);
	delete[] Y;
	delete[] Z;
	return true;
}
void main(){
	float temp,dst;
	PointX A;
	PointX B;
	PointX X[4];
int m;
cout<<"请输入要比较的点的个数"<<"m=";
cin>>m;
	for(int i=0;i<m;i++){
		cout<<"P"<<i+1<<endl;
		cout<<"x:";
		cin>>temp;
		X[i].x=temp;
		cout<<"y:";
		cin>>temp;
		X[i].y=temp;
		X[i].ID=i+1;
		cout<<"******************"<<endl;
	}
	Cpair2(X,4,A,B,dst);
	cout<<"P"<<A.ID<<"<--->"<<"P"<<B.ID<<'\n'<<"distance:"<<dst<<endl;
	//delete A;,B,X[N];
}