新建 文本文档.txt

求最近点对问题

#include <vector>
using namespace std;
typedef struct
{
	int x;					//x坐标
	int y;					//y坐标
}NEARTEAM;
typedef struct				//
{
	int indexx;				//第一个点的索引
	int indexy;				//第二个点的索引
}INDEX;
void InitTeam(vector <NEARTEAM> &team);
//从键盘初始化点
void Print(vector <NEARTEAM> &team);
//输出所有点
vector<INDEX> BruteForce(vector <NEARTEAM> &team);
//蛮力法求最近两点
int Power2(NEARTEAM A,NEARTEAM B);
//求这两个点的平方
void main()
{
	vector <NEARTEAM> team;//保存结果
	InitTeam(team);
	Print(team);
//	printf("下表索引是\n%d,%d",
//		BruteForce(team).indexx,
//		BruteForce(team).indexy);
}
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);
	}
}
vector<INDEX> BruteForce(vector <NEARTEAM> &team)
{
	INDEX temp;
	vector <INDEX> index;			//保存所有最近点的向量,因为有可能两个点距离相同
	int dmin=0;		//保存临时的最小值
	int d=0;
	bool first=true;//是不是第一次比较
	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]);
				first=false;
			}
			else
			{
				d=Power2(team[i],team[j]);
				if(d<dmin)
				{
					dmin=d;			//将这个值编程最小的
					temp.indexx=i;
					temp.indexy=j;
				}
			}
		}
	}
	temp.indexx+=1;//因为下标是从零开始的
	temp.indexy+=1;//因为下标是从零开始的
//	return temp;
	return index;
}
int Power2(NEARTEAM A,NEARTEAM B)
{
	return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
}