游客 注册 | 登录
中文 | En

3163 - 最接近点对问题

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。严格地说，最接近点对可能多于1对。为了简单起见，这里只限于找其中的一对。

题目输入

第一行：点数n

第二行至第n行，每个点

题目输出

第一行：输出最接近点对

第二行：输出最近点对距离

输入/输出样例

输入格式

5
18.6,34.27
94.74,37.63
15.07,80.4
51.98,10.72
38.67,93.78

输出格式

(15.07,80.4)(38.67,93.78)
27.129

C++解答

////2d10-2 二维最邻近点对问题
//
//#include<time.h>
//#include<iostream> 
//#include<cmath>
//
//using namespace std;
//const int M=50;
//
////用类PointX和PointY表示依x坐标和y坐标排好序的点
//class PointX {
//public: 
//	int operator<=(PointX a)const
//	{ return (x<=a.x); }
//	int ID; //点编号
//	float x,y; //点坐标 
//};
//
//class PointY { 
//public: 
//	int operator<=(PointY a)const
//	{ return(y<=a.y); }
//	int p; //同一点在数组x中的坐标 
//	float x,y; //点坐标
//};
//
//float Random();
//template <class Type>
//float dis(const Type&u,const Type&v); 
//
//bool Cpair2(PointX X[], int n,PointX& a,PointX& b, float& d);
//void closest(PointX X[],PointY Y[],PointY Z[], int l, int r,PointX& a,PointX& b,float& d);
//
//template <typename Type> 
//void Copy(Type a[],Type b[], int left,int right);
//
//template <class Type>
//void Merge(Type c[],Type d[],int l,int m,int r);
//
//template <class Type>
//void MergeSort(Type a[],Type b[],int left,int right);
//
//int main()
//{ 
//	srand((unsigned)time(NULL));
//	int length;
//
//	cout<<"请输入点对数：";
//	cin>>length;
//
//	PointX X[M];
//	cout<<"随机生成的二维点对为："<<endl;
//
//	for(int i=0;i<length;i++)
//	{
//		X[i].ID=i;
//		X[i].x=Random();
//		X[i].y=Random();
//		cout<<"("<<X[i].x<<","<<X[i].y<<") ";
//	}
//
//	PointX a; 
//	PointX b; 
//	float d;
//
//	Cpair2(X,length,a,b,d); 
//
//	cout<<endl;
//	cout<<"最邻近点对为：("<<a.x<<","<<a.y<<")和("<<b.x<<","<<b.y<<") "<<endl;
//	cout<<"最邻近距离为： "<<d<<endl;
//	getchar();
//	return 0;
//}
//
//float Random()
//{
//	float result=rand()%10000;
//	return result*0.01;
//}
//
////平面上任意两点u和v之间的距离可计算如下
//template <class Type>
//inline float dis(const Type& u,const Type& v)
//{
//	float dx=u.x-v.x;
//	float dy=u.y-v.y; 
//	return sqrt(dx*dx+dy*dy); 
//}
//
//bool Cpair2(PointX X[], int n,PointX& a,PointX& b,float& d)
//{
//	if(n<2) return false;
//
//	PointX* tmpX = new PointX[n];
//	MergeSort(X,tmpX,0,n-1);
//
//	PointY* Y=new PointY[n]; 
//	for(int i=0;i<n;i++) //将数组X中的点复制到数组Y中
//	{ 
//		Y[i].p=i;
//		Y[i].x=X[i].x;
//		Y[i].y=X[i].y;
//	} 
//
//	PointY* tmpY = new PointY[n];
//	MergeSort(Y,tmpY,0,n-1);
//
//	PointY* Z=new PointY[n];
//	closest(X,Y,Z,0,n-1,a,b,d); 
//
//	delete []Y; 
//	delete []Z;
//	delete []tmpX;
//	delete []tmpY;
//	return true; 
//}
//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=dis(X[l],X[r]);
//		return; 
//	} 
//
//	if(r-l==2) //3点的情形 
//	{
//		float d1=dis(X[l],X[l+1]);
//		float d2=dis(X[l+1],X[r]); 
//		float d3=dis(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; 
//	} 
//
//	//多于3点的情形，用分治法 
//	int m=(l+r)/2; 
//	int f=l,g=m+1; 
//
//	//在算法预处理阶段，将数组X中的点依x坐标排序，将数组Y中的点依y坐标排序
//	//算法分割阶段，将子数组X[l:r]均匀划分成两个不想交的子集，取m=(l+r)/2
//	//X[l:m]和X[m+1:r]就是满足要求的分割。
//	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);//重构数组Y
//
//	//d矩形条内的点置于Z中
//	int k=l; 
//	for(int i=l;i<=r;i++)
//	{
//		if(fabs(X[m].x-Y[i].x)<d)
//		{ 
//			Z[k++]=Y[i]; 
//		}
//	}
//
//	//搜索Z[l:k-1]
//	for(int i=l;i<k;i++) 
//	{ 
//		for(int j=i+1;j<k && Z[j].y-Z[i].y<d;j++) 
//		{ 
//			float dp=dis(Z[i],Z[j]);
//			if(dp<d) 
//			{ 
//				d=dp; 
//				a=X[Z[i].p];
//				b=X[Z[j].p]; 
//			}
//		}
//	} 
//}
//
//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];
//		}
//	}
//}
//
//template <class Type>
//void MergeSort(Type a[],Type b[],int left,int right)
//{
//	if(left<right)
//	{
//		int i = (left + right)/2;
//		MergeSort(a,b,left,i);
//		MergeSort(a,b,i+1,right);
//		Merge(a,b,left,i,right);//合并到数组b
//		Copy(a,b,left,right);//复制回数组a		
//	}
//}
//
//template <typename Type> 
//void Copy(Type a[],Type b[], int left,int right)
//{
//	for(int i=left;i<=right;i++) 
//		a[i]=b[i]; 
//}


#include<iostream> 
#include<cmath>

using namespace std;
const int M=50;

//用类PointX和PointY表示依x坐标和y坐标排好序的点
class PointX 
{
public: 
	int operator<=(PointX a)const
	{ 
		return (x<=a.x); 
	}
	int ID; //点编号
	float x,y; //点坐标 
};

class PointY
{ 
public: 
	int operator<=(PointY a)const
	{ 
		return(y<=a.y);
	}
	int p; //同一点在数组x中的坐标 
	float x,y; //点坐标
};

int main()
{ 
	int length;
	bool Cpair2(PointX X[], int n,PointX& a,PointX& b,float& d);
	//	cout<<"请输入点对数：";
	cin>>length;
	PointX X[M];
	//	cout<<"请输入"<<length<<"对点:";
	for(int i=0;i<length;i++)
		scanf("%f,%f",&X[i].x,&X[i].y);
	PointX a; 
	PointX b; 
	float d;

	Cpair2(X,length,a,b,d); 

	//cout<<endl;
	//cout<<"最邻近点对为：";
	cout<<"("<<a.x <<","<<a.y <<")(" <<b.x <<","<<b.y <<")"<<endl;

	//cout<<"最邻近距离为： ";
	cout<<d<<endl;

	return 0;
}

//平面上任意两点u和v之间的距离计算如下
template <class Type>
inline float dis(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)//重构数组Y
{
	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=dis(X[l],X[r]);
		return; 
	} 

	if(r-l==2) //3点的情形 
	{
		float d1=dis(X[l],X[l+1]);
		float d2=dis(X[l+1],X[r]); 
		float d3=dis(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; 
	} 

	//多于3点的情形，用分治法 
	int m=(l+r)/2; 
	int f=l,g=m+1; 

	//在算法预处理阶段，将数组X中的点依x坐标排序，将数组Y中的点依y坐标排序
	//算法分割阶段，将子数组X[l:r]均匀划分成两个不想交的子集，取m=(l+r)/2
	//X[l:m]和X[m+1:r]就是满足要求的分割。
	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);//重构数组Y

	//d矩形条内的点置于Z中
	int k=l; 

	for(int i1=l;i1<=r;i1++)
	{
		if(fabs(X[m].x-Y[i1].x)<d)
		{ 
			Z[k++]=Y[i1]; 
		}
	}

	//搜索Z[l:k-1]
	for(int i2=1;i2<k;i2++) 
	{ 
		for(int j=i2+1;j<k && Z[j].y-Z[i2].y<d;j++) 
		{ 
			float dp=dis(Z[i2],Z[j]);
			if(dp<d) 
			{ 
				d=dp; 
				a=X[Z[i2].p];
				b=X[Z[j].p]; 
			}
		}
	} 
}


template <class Type>
void MergeSort(Type a[],Type b[],int left,int right)
{
	if(left<right)
	{
		int i = (left + right)/2;
		MergeSort(a,b,left,i);
		MergeSort(a,b,i+1,right);
		Merge(a,b,left,i,right);//合并到数组b
		Copy(a,b,left,right);//复制回数组a		
	}
}

template <typename Type> 
void Copy(Type a[],Type b[], int left,int right)
{
	for(int i=left;i<=right;i++) 
		a[i]=b[i]; 
}

bool Cpair2(PointX X[], int n,PointX& a,PointX& b,float& d)
{
	if(n<2) return false;

	PointX* tmpX = new PointX[n];
	MergeSort(X,tmpX,0,n-1);

	PointY* Y=new PointY[n]; 
	for(int i=0;i<n;i++) //将数组X中的点复制到数组Y中
	{ 
		Y[i].p=i;
		Y[i].x=X[i].x;
		Y[i].y=X[i].y;
	} 

	PointY* tmpY = new PointY[n];
	MergeSort(Y,tmpY,0,n-1);

	PointY* Z=new PointY[n];
	closest(X,Y,Z,0,n-1,a,b,d); 

	delete []Y; 
	delete []Z;
	delete []tmpX;
	delete []tmpY;
	return true; 
}
请先登陆