C++_最接近点对问题

问题描述、

问题描述：最接近点对问题，给定平面上n个点，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。

设计思路

设计思路：设S中的点为平面上的点，它们都有2个坐标值x和y。为了将平面上点集S线性分割为大小大致相等的2个子集S1和S2，我们选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1={p∈S|px≤m}和S2={p∈S|px>m}。从而使S1和S2分别位于直线l的左侧和右侧，且S=S1∪S2。由于m是S中各点x坐标值的中位数，因此S1和S2中的点数大致相等。递归地在S1和S2上解最接近点对问题，我们分别得到S1和S2中的最小距离d1和d2。现设d=min(d1,d2)。若S的最接近点对(p,q)之间的距离d(p,q)<d则p和q必分属于S1和S2。不妨设p∈S1，q∈S2。那么p和q距直线l的距离均小于d。因此，我们若用P1和P2分别表示直线l的左边和右边的宽为d的2个垂直长条，则p∈S1，q∈S2，如图所示:

距直线l的距离小于d的所有点

在一维的情形，距分割点距离为d的2个区间(m-d,m](m,m+d]中最多各有S中一个点。因而这2点成为唯一的末检查过的最接近点对候选者。二维的情形则要复杂些，此时，P1中所有点与P2中所有点构成的点对均为最接近点对的候选者。在最坏情况下有n2/4对这样的候选者。但是P1和P2中的点具有以下的稀疏性质，它使我们不必检查所有这n^2/4对候选者。考虑P1中任意一点p,它若与P2中的点q构成最接近点对的候选者，则必有d(p,q)<d。满足这个条件的P2中的点有多少个呢？容易看出这样的点一定落在一个d×2d的矩形R中，如下图所示:

包含点q的dX2d矩形R

由d的意义可知P2中任何2个S中的点的距离都不小于d。由此可以推出矩形R中最多只有6个S中的点。事实上，我们可以将矩形R的长为2d的边3等分，将它的长为d的边2等分，由此导出6个（d/2）×（2d/3）的矩形。如左图所示:

矩阵R中点的稀疏性

若矩形R中有多于6个S中的点，则由鸽舍原理易知至少有一个δ×2δ的小矩形中有2个以上S中的点。设u,v是这样2个点，它们位于同一小矩形中，则：

因此d(u,v)≤5d/6<d 。这与d的意义相矛盾。也就是说矩形R中最多只有6个S中的点。图4(b)是矩形R中含有S中的6个点的极端情形。由于这种稀疏性质，对于P1中任一点p，P2中最多只有6个点与它构成最接近点对的候选者。因此，在分治法的合并步骤中，我们最多只需要检查6×n/2=3n对候选者，而不是n^2/4对候选者。这是否就意味着我们可以在O(n)时间内完成分治法的合并步骤呢？现在还不能作出这个结论，因为我们只知道对于P1中每个S1中的点p最多只需要检查P2中的6个点，但是我们并不确切地知道要检查哪6个点。为了解决这个问题，我们可以将p和P2中所有S2的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中，所以它们在直线l上的投影点距p在l上投影点的距离小于d。由上面的分析可知，这种投影点最多只有6个。因此，若将P1和P2中所有S的点按其y坐标排好序，则对P1中所有点p，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者，对P1中每一点最多只要检查P2中排好序的相继6个点。

数据结构：

a[N]：存放随机生成的点集

b[N]，c[N]：分别存放分块后的两部分点集

t[1],q[2],p[2],o[2]：工作数组

d：两点直接距离

dmin1：第一部分中最近两点之间距离

dmin2：第二部分中最近两点之间距离

dmin：最近两点之间距离

算法描述：

For i=0 to N
a[i].x<-rand()%101,a[i].y<-rand()%101//随机生成N个空间坐标点
For i=0 to N
If(a[i].x<N/2) then
{b[j]=a[i];j++}
Else
{c[k]=a[i];k++}
For i=0 to j
For r=i+1 to j
d=sqar((b[i].x-b[r].x)²+(b[i].y-b[r].y)²)
If(d<dmin1) then
{dmin1=d;p[0]=b[i];p[1]=b[r]}
For i=0 to k
For r=i+1 to k
d=sqar((c[i].x-c[r].x)²+(c[i].y-c[r].y)²)
If(d<dmin2) then
{dmin2=d;q[0]=c[i];q[1]=c[r]}
dmin=min{dmin1,dmin2};o[2]=min{p[2],q[2]}
for i=0 to j
if((c[r].x-N/2)<dmin) and (c[r].y-b[i].y)<dmin) then
{d=d(c[r],b[i]);o[0]=b[1];o[1]=c[r]}
If(d<dmin) then
dmin=d;
Output(d,o[2])

测试用例：随机输入100个点为：(41,85) (72,38) (80,69) (65,68) (96,22) (49,67) (51,61) (63,87) (66,24) (80,83) (71,60) (64,52) (90,60) (49,31) (23,99) (94,11) (25,24) (51,15) (13,39) (67,97) (19,76) (12,33) (99,18) (92,35) (74,0) (95,71) (39,33) (39,32) (37,45) (57,71) (95,5) (71,24) (86,8) (51,54) (74,24) (75,70) (33,63) (29,99) (58,94) (52,13) (35,99) (46,57) (71,23) (17,3) (94,48) (77,18) (83,11) (83,25) (59,62) (2,78) (86,7) (94,65) (80,32) (39,84) (60,65) (72,61) (58,84) (8,72) (12,19) (47,49) (49,59) (71,52) (34,22) (21,20) (92,33) (80,39) (74,9) (28,97) (100,93) (29,25) (4,66) (79,81) (98,21) (91,62) (82,4) (59,100) (34,1) (51,80) (92,69) (77,39) (38,97) (51,34) (35,19) (22,1) (67,9) (90,31) (82,11) (51,84) (78,70) (74,42) (100,88) (53,80) (57,62) (32,51) (48,63) (92,46) (4,61) (31,98) (69,52) (88,20)
运行得空间内最接近点对为：

点：(71,24) 点：(71,23)

两点之间距离为 1

设计及测试过程

第一步：提出问题；

第二步：问题转换；

第三步：算法构思；

第四步：伪码描述；

第五步：代码编写；

第六步：代码测试；

第七步：代码修正；

#include <iostream>
using namespace std;
#define N 100
struct node
{
	float x;
	float y;
}a[N],b[N],c[N],t[1],q[2],p[2],o[2];
int main()
{
	int i,r,j=0,k=0;
	float d,dmin1=200,dmin2=200,dmin;
	for(i=0;i<N;i++)
	{
		a[i].x=rand()%101;
		a[i].y=rand()%101;
	}
	cout<<"随机生成空间内100个点分别为"<<endl;
	for(i=0;i<N;i++)
		cout<<"("<<a[i].x<<","<<a[i].y<<") ";
	for(i=0;i<N;i++)
	{
		if(a[i].x<50)
		{
			b[j]=a[i];
			j++;
		}
		else
		{
			c[k]=a[i];
			k++;
		}
	}
	for(i=0;i<j;i++)
	{
		for(r=i+1;r<j;r++)
		{
			d=sqrt((b[i].x-b[r].x)*(b[i].x-b[r].x)+(b[i].y-b[r].y)*(b[i].y-b[r].y));
			if(d<dmin1)
			{
				dmin1=d;
				p[0]=b[i];
				p[1]=b[r];
			}
		}
	}
	for(i=0;i<k;i++)
	{
		for(r=i+1;r<k;r++)
		{
			d=sqrt((c[i].x-c[r].x)*(c[i].x-c[r].x)+(c[i].y-c[r].y)*(c[i].y-c[r].y));
			if(d<dmin2)
			{
				dmin2=d;
				q[0]=c[i];
				q[1]=c[r];
			}
		}
	}
	if(dmin1<dmin2)
	{
		dmin=dmin1;
		o[0]=p[0];
		o[1]=p[1];
	}
	else
	{
		dmin=dmin2;
		o[0]=q[0];
		o[1]=q[1];
	}
	for(i=0;i<j;i++)
		if((b[i].x-50)*(b[i].x-50)<dmin*dmin)
		{
			for(r=0;r<k;r++)
			{
				if((c[r].x-50)*(c[r].x-50)<dmin*dmin&&(c[r].y-b[i].y)*(c[r].y-b[i].y)<dmin*dmin)
				{
					d=sqrt((b[i].x-c[r].x)*(b[i].x-c[r].x)+(b[i].y-c[r].y)*(b[i].y-c[r].y));
					if(d<dmin)
					{
						dmin=d;
						o[0]=b[i];
						o[1]=c[r];
					}
				}
			}
		}
	cout<<endl<<"空间内最接近点对为"<<endl;
	for(i=0;i<2;i++)
		cout<<"点：("<<o[i].x<<","<<o[i].y<<") ";
	cout<<endl<<"两点之间距离为 ";
	cout<<dmin;
	system("pause");
	return 0;
}

原文链接：https://blog.csdn.net/weixin_42733218/article/details/83350502