给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。1、一维最接近点对问题采用分治法思想，考虑将所给的n个点的集合S分成2个子集S1和S2，每个子集中约有n/2个点，然后在每个子集中递归地求其最接近的点对。 2、二维最接近点对问题将以上过程推广到

10/4/2018 - 11:14 AM

给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。 1、一维最接近点对问题采用分治法思想，考虑将所给的n个点的集合S分成2个子集S1和S2，每个子集中约有n/2个点，然后在每个子集中递归地求其最接近的点对。 2、二维最接近点对问题将以上过程推广到

给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。 1、一维最接近点对问题采用分治法思想，考虑将所给的n个点的集合S分成2个子集S1和S2，每个子集中约有n/2个点，然后在每个子集中递归地求其最接近的点对。 2、二维最接近点对问题将以上过程推广到二维最接近点对问题，设S中的点为平面上的点，它们都有2个坐标值x和y。为了将平面上点集S线性分割为大小大致相等的2个子集S1和S2，我们选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为

Cpair1.cpp

//2d10-1 一维最邻近点对问题
#include "stdafx.h"
#include <ctime>
#include <iostream> 
using namespace std; 
 
const int L=100;
//点对结构体
struct Pair
{
	float d;//点对距离
	float d1,d2;//点对坐标
};
float Random();
int input(float s[]);//构造S
float Max(float s[],int p,int q);
float Min(float s[],int p,int q);
template <class Type>
void Swap(Type &x,Type &y);
template <class Type>
int Partition(Type s[],Type x,int l,int r);
Pair Cpair(float s[],int l,int r);
 
int main()
{
	srand((unsigned)time(NULL));
	int m;
	float s[L];
	Pair d;
	m=input(s);
	d=Cpair(s,0,m-1);
	cout<<endl<<"最近点对坐标为： (d1:"<<d.d1<<",d2:"<<d.d2<<")";
	cout<<endl<<"这两点距离为： "<<d.d<<endl;
	return 0;
}
 
 
float Random()
{
	float result=rand()%10000;
	 return result*0.01;
}
 
int input(float s[])
{
	int length;
	cout<<"输入点的数目： ";
	cin>>length;
	cout<<"点集在X轴上坐标为：";
	for(int i=0;i<length;i++)
	{
		s[i]=Random();
		cout<<s[i]<<" ";
	}
	
	return length;
}
 
 
float Max(float s[],int l,int r)//返回s[]中的最大值
{
	float s_max=s[l];
	for(int i=l+1;i<=r;i++)
		if(s_max<s[i])
			s_max=s[i];
	return s_max;
}
 
float Min(float s[],int l,int r)//返回s[]中的最小值
{
	float s_min=s[l];
	for(int i=l+1;i<=r;i++) 
		if(s_min>s[i])
			s_min=s[i];
	return s_min;
}
 
template <class Type>
void Swap(Type &x,Type &y)
{
	Type temp = x;
	x = y;
	y = temp;
}
 
template <class Type>
int Partition(Type s[],Type x,int l,int r)
{
	int i = l - 1,j = r + 1;
 
	while(true)
	{
		while(s[++i]<x && i<r);
		while(s[--j]>x);
		if(i>=j)
		{
			break;
		}
		Swap(s[i],s[j]);
	}
	return j;
}
 
//返回s[]中的具有最近距离的点对及其距离
Pair Cpair(float s[],int l,int r)
{
	Pair min_d={99999,0,0};//最短距离
 
	if(r-l<1) return min_d;
	float m1=Max(s,l,r),m2=Min(s,l,r);
 
	float m=(m1+m2)/2;//找出点集中的中位数
 
	//将点集中的各元素按与m的大小关系分组
	int j = Partition(s,m,l,r);
 
	Pair d1=Cpair(s,l,j),d2=Cpair(s,j+1,r);//递归
	float p=Max(s,l,j),q=Min(s,j+1,r);
 
	//返回s[]中的具有最近距离的点对及其距离
	if(d1.d<d2.d)
	{
		if((q-p)<d1.d)
		{
			min_d.d=(q-p);
			min_d.d1=q;
            min_d.d2=p;
			return min_d;
		}
		else return d1;
	}
	else
	{
		if((q-p)<d2.d)
		{
			min_d.d=(q-p);
			min_d.d1=q;
            min_d.d2=p;
			return min_d;
		}
		else return d2;
	}
}

Cpair2.cpp

//2d10-2 二维最邻近点对问题
#include "stdafx.h"
#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;
 
	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]; 
}

Cacher is the code snippet organizer for pro developers

We empower you and your team to get more done, faster