最近对.cpp

求最近点对问题

#include <vector>
#include <math.h>
#include <time.h>
using namespace std;
typedef struct
{
	int x;					//x坐标
	int y;					//y坐标
	int index;				//保存下标
}NEARTEAM;
typedef struct				
{
	int indexx;				//第一个点的索引
	int indexy;				//第二个点的索引
	int temp;				//保存线段长度
}INDEX;						//保存了最近点的索引
void InitTeam(vector <NEARTEAM> &team);
//从键盘初始化点
void Print(vector <NEARTEAM> &team);
//输出所有点
void BruteForce(vector <NEARTEAM> &team,vector <INDEX> &index,int &times);
//蛮力法求最近两点
int Power2(NEARTEAM A,NEARTEAM B);
//求这两个点的平方
void Divide(vector<NEARTEAM> X,int l,int r,NEARTEAM &a,NEARTEAM &b,int &d,int &times);
//分治法求最近点问题
void SortX(vector  <NEARTEAM> &team);
vector <INDEX> result;//保存分治法求的结果
void FindSame(vector <NEARTEAM> team,int d,int &times);
void ProPoint(NEARTEAM &Point);
bool PointIsSame(NEARTEAM x,NEARTEAM y);
//判断两个点是否相同
//产生一个随机点
void main()
{
	vector <NEARTEAM> team;//保存结果
	vector <INDEX> index;//	保存下标是值
	NEARTEAM		temp;
	int times=0;
	bool first=true;
	///	InitTeam(team);
	srand(time(NULL));//产生不同的随机数
	printf("输入产生的随即点的个数:\n");
	int number=0;
	scanf("%d",&number);
	for(int j=0;j<number;j++)
	{	
		if(first)
		{
			ProPoint(temp);
			team.push_back(temp);
			first=false;
		}
		ProPoint(temp);
		for(int k=0;k<team.size()-1;k++)
		{
			if(PointIsSame(team[k],temp))
			{
				ProPoint(temp);
				k=0;
			}
		}
		team.push_back(temp);
	}
	SortX(team);
	//建立索引
	for(int i=0;i<team.size();i++)
	{
		 team[i].index=i;
	}
	Print(team);
	BruteForce(team,index,times);
	printf("蛮力法查找的结果是:\n");
	for(i=0;i<index.size();i++)
	{
		printf("%d,%d %d,%d长度是%d\n",team[index[i].indexx-1].x,team[index[i].indexx-1].y,
			team[index[i].indexy-1].x,team[index[i].indexy-1].y,index[i].temp);
	}
	printf("计算次数是%d\n",times);
	NEARTEAM A,B;
	times=0;
	int d=0;
	Divide(team,0,team.size()-1,A,B,d,times);
	//	printf("最近点的元素是:\n%d,%d  %d,%d 长度是%d\n",
	//	A.x,A.y,B.x,B.y,d);
	FindSame(team,d,times);
	printf("分治法查找结果是:\n");
	for(i=0;i<result.size();i++)
	{
		printf("%d,%d %d,%d长度是%d\n",team[result[i].indexx-1].x,team[result[i].indexx-1].y,
			team[result[i].indexy-1].x,team[result[i].indexy-1].y,result[i].temp);
	}
	printf("计算次数是%d\n",times);
}
void InitTeam(vector <NEARTEAM> &team)
{
	NEARTEAM  temp;//临时变量
	printf("请输入一个整数对,整数之间用空格分离!\n输入完毕已#号结束\n");
	char ch;
	do
	{
		scanf("%d %d",
			&temp.x,&temp.y);
		team.push_back(temp);
		ch=getc(stdin);
		if(ch=='#')
		{
			break;
		}
	}while(true);
}
void Print(vector <NEARTEAM> &team)
{
	printf("所有的点是:\n");
	for(int i=0;i<team.size();i++)
	{
		printf("%d,%d\n",team[i].x,team[i].y);
	}
}
void BruteForce(vector <NEARTEAM> &team,vector <INDEX> &index,int &times)
{
	INDEX temp;
	int   dmin=0;
	bool  first=true;
	int   d=0;
	if(team.size()>1)
	{
		for(int i=0;i<team.size()-1;i++)
		{
			for(int j=i+1;j<team.size();j++)
			{
				if(first)//如果是是第一次
				{
					dmin=Power2(team[i],team[j]);
					temp.indexx=i+1;
					temp.indexy=j+1;
					temp.temp=dmin;
					index.push_back(temp);
					first=false;
				}
				else
				{
					d=Power2(team[i],team[j]);
					times+=2;
					if(d<dmin)//如果发现了还小的
					{
						//当前所有的最小元素清空
						//				for(int k=0;k<=index.size()+1;k++)
						//		{
						//			times++;
						//			index.pop_back();
						//		}
						index.clear();
						//	printf("长度=%d",index.size());
						temp.indexx=i+1;
						temp.indexy=j+1;
						temp.temp=d;
						index.push_back(temp);
						dmin=d;					//变成最小的
					}
					else
					{
						if(d==dmin)//如果后面有和当前最小元素相同的就加进来
						{
							temp.indexx=i+1;
							temp.indexy=j+1;
							temp.temp=dmin;
							index.push_back(temp);                                                                                                                                                                                             
						}
					}
				}
			}
		}
	}
	else
	{
		temp.indexx=1;
		temp.indexy=1;
		index.push_back(temp);
	}
}
int Power2(NEARTEAM A,NEARTEAM B)
{
	return (A.x-B.x)*(A.x-B.x)+
		(A.y-B.y)*(A.y-B.y);
}
void SortX(vector  <NEARTEAM> &team)
{
	int i=0;
	int j=0;//用于外层循环
	NEARTEAM t;
	int flag;
	for(j=0;j<team.size()-1;j++)//遍历数组中的n-1个元素
	{
		flag=0;//
		for(i=0;i<team.size()-j-1;i++)//从前n-j-1中找到最大的元素
		{
			if(team[i].x>=team[i+1].x)
			{
				t=team[i];
				team[i]=team[i+1];
				team[i+1]=t;
				flag=1;//用元素交换,标志位移
			}
		}
		if(flag==0)
		{
			break;
		}
	}
}
NEARTEAM Z[100];
void Divide(vector<NEARTEAM> X,int l,int r,NEARTEAM &a,NEARTEAM &b,int &d,int &times)
{
	int i=0;
	if(r-l==1)//如果距离为一直接计算
	{
		a=X[l];
		b=X[r];
		d=Power2(X[l],X[r]);
		times+=2;
		return;
	}
	if(r-l==2)//如果距离为二
	{
		int	 d1=Power2(X[l],X[l+1]);
		int  d2=Power2(X[l+1],X[r]);
		int  d3=Power2(X[l],X[r]);
		times+=6;
		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;
	Divide(X,l,m,a,b,d,times);		
	int dr=0;
	NEARTEAM ar, br;
	Divide(X,m+1,r,ar,br,dr,times);
	if (dr<d) 
	{
		a=ar;
		b=br;
		d=dr;
	}
	// 距离小于d的点放入Z
	int k=l; 
	for(i=l;i<=r;i++)
	{
		if(fabs(X[m].x-X[i].x)<=d)
		{
			Z[k++]=X[i];
		}
	}
	//通过检查Z[l:k-1]中的所有点对,寻找较近的点对
	for(i=l;i<=m;i++)//i<m保证为左边的点
	{
		for(int j=m+1;j<k&&
			fabs((Z[j].y-Z[i].y))<d;j++)
		{
			int  dp=Power2(Z[i],Z[j]);
			times+=2;
			if(dp<d)
			{
				d=dp;
				a=X[Z[i].index];
				b=X[Z[j].index];
			}
		}
	}
	return;
}
void FindSame(vector <NEARTEAM> team,int d,int &times)
{
	INDEX temp;
	for(int i=0;i<team.size()-1;i++)//查找和最短距离相同的点
	{
		for(int j=i+1;j<team.size();j++)
		{
			times++;
			if(Power2(team[i],team[j])==d)
			{
				temp.indexx=i+1;
				temp.indexy=j+1;
				temp.temp=d;
				result.push_back(temp);
			}
		}
	}
}
void ProPoint(NEARTEAM &Point)
{
	int x=0;
	int y=0;
	x=rand()%50;
	y=rand()%50;
	Point.x=x;
	Point.y=y;
}
bool PointIsSame(NEARTEAM x,NEARTEAM y)
{
	return (x.x==y.x&&x.y==y.y);
}