cpair1.cpp

本程序可以在输入n点后

#include "iostream.h"
#define M 20

struct cpair//表示具有最近距离的点对(d1,d2)的距离dist
{
	float dist;
	float d1,d2;
};

int input(float s[],int n)//s[]为一维点集，n为s[]中的元素个数
{
	cout<<"输入一维点集的各元素(以-1结束):\n";
	n=0;
	cin>>s[n];
	while(s[n]!=-1)
	{
		n++;
		cin>>s[n];
	}
	return n;
}

float max(float s[],int b,int e)//返回s[b]到s[e]中的最大值
{
	float m1=s[b];
	for(int i=b+1;i<=e;i++)	if(m1<s[i]) m1=s[i];
	return m1;
}

float min(float s[],int b,int e)//返回s[b]到s[e]中的最小值
{
	float m1=s[b];
	for(int i=b+1;i<=e;i++) if(m1>s[i]) m1=s[i];
	return m1;
}

//返回s[]中的具有最近距离的点对及其距离
cpair cpair1(float s[],int n)
{
	cpair temp={1000,0,0};
	//当点集中元素的个数不足2时,返回具有无穷大的dist值(此处设为1000)的temp
	if(n<2) return temp;
	float m1=max(s,0,n-1),m2=min(s,0,n-1);
	float m=(m1+m2)/2;//找出点集中的中位数
	int j=0,k=0;
	//将点集中的各元素按与m的大小关系分组
	float s1[M],s2[M];
	for(int i=0;i<n;i++)
	{
		if(s[i]<=m) {s1[j]=s[i];j++;}
		else {s2[k]=s[i];k++;}
	}	
	cpair d1=cpair1(s1,j),d2=cpair1(s2,k);//递归
	float p=max(s1,0,j-1),q=max(s2,0,k-1);
	//返回s[]中的具有最近距离的点对及其距离
	if(d1.dist<d2.dist)
	{
		if((q-p)<d1.dist)
		{
			temp.dist=(q-p);
			temp.d1=q;
            temp.d2=p;
			return temp;
		}
		else return d1;
	}
	else
	{
		if((q-p)<d2.dist)
		{
			temp.dist=(q-p);
			temp.d1=q;
            temp.d2=p;
			return temp;
		}
		else return d2;
	}
}
void main()
{
	int n,m;
	float s[M];
	cpair dist;
	m=input(s,n);
	dist=cpair1(s,m);
	cout<<"\n该一维点集中最近点对为("<<dist.d1<<","<<dist.d2<<"),其距离为"<<dist.dist<<endl;
}