最近点对问题.pdf

文档介绍：最近点对问题

：

一、问题描述和分析
最近点对问题的提法是：给定平面上 n 个点，找其中的一对点，使得在 n 个点组成的
所有点对中，该点对ruct 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(<)
{
if((q-p)<)
{