#include <stdio.h>
#include <math.h>
#define false 0
#define true 1
class PointX
{
public:
int operator <= (PointX a)const
{return x<=a.x;}
// private:
int ID;//点编号
float x,y;
};
class PointY
{
public:
int operator <= (PointY a)const
{return y<=a.y;}
// private:
int p;//同一点在数组X中坐标
float x,y;
};
template <class Type>
inline float distance(const Type u,const Type v)
{
float dx=u.x-v.x;
float dy=u.y-v.y;
return sqrt(dx*dx+dy*dy);
}
template <class Type>
void Merge(Type *c,Type *d,int l,int m,int r)
{//合并c[l:m],c[m+1:r]到d[l,r]
int i=l,j=m+1,k=l,q;
while ((i<=m)&&(j<=r))
if (c[i]<=c[j])d[k++]=c[i++];
else d[k++]=c[j++];
if(i>m)
for (q=j;q<=r;q++)d[k++]=c[q];
else
for (q=i;q<=m;q++)d[k++]=c[q];
}
template <class Type>
void MergePass(Type *x,Type *y,int s,int n)
{//合并长度为s的相邻子数组
int j,i=0;
while (i<=n-2*s)
{
Merge(x,y,i,i+s-1,i+2*s-1);
i=i+2*s;
}
//剩下元素个数少于2s
if (i+s<n)
Merge(x,y,i,i+s-1,n-1);
else
for(j=i;j<=n-1;j++)y[j]=x[j];
}
template <class Type>
void MergeSort(Type *a,int n)
{
Type *b=new Type[n];
int s=1;
while (s<n)
{
MergePass(a,b,s,n);
s+=s;
MergePass(b,a,s,n);
s+=s;
}
}
void closest(PointX *X,PointY *Y,PointY *Z,int l,int r,
PointX &a,PointX &b,float &d)
{
int i,j,k,m,f,g;
float dr,dp,d1,d2,d3;
PointX ar,br;
if (r-l==1)//只有2点
{
a=X[l];
b=X[r];
d=distance(X[l],X[r]);
return;
}
if (r-l==2)//3点情况
{
d1=distance(X[l],X[l+1]);
d2=distance(X[l+1],X[r]);
d3=distance(X[l],X[r]);
if ((d1<=d2)&&(d1<=d3))
{
a=X[l];
b=X[l+1];
d=d1;
return;
}
if ((d2<=d1)&&(d2<=d3))
{
a=X[l+1];
b=X[r];
d=d2;
return;
}
if ((d3<=d2)&&(d3<=d1))
{
a=X[l];
b=X[r];
d=d3;
return;
}
}
//多于3点
m=(l+r)/2;
f=l;
g=m+1;
for(i=l;i<=r;i++)
if (Y[i].p>m)Z[g++]=Y[i];
else Z[f++]=Y[i];
closest(X,Z,Y,l,m,a,b,d);
closest(X,Z,Y,m+1,r,ar,br,dr);
if (dr<d)
{
a=ar;b=br;d=dr;
}
Merge(Z,Y,l,m,r);//重构数组Y
k=l;
for (i=l;i<=r;i++)
if (fabs(Y[m].x-Y[i].x)<d) Z[k++]=Y[i];
for (i=l;i<k;i++)
for(j=i+1;(j<k)&&(Z[j].y-Z[i].y<d);j++)
{
dp=distance(Z[i],Z[j]);
if (dp<d)
{
d=dp;
a=X[Z[i].p];
b=X[Z[j].p];
}
}
}
int Cpair2(PointX *X,int n,PointX &a,PointX &b,float &d)
{
int i;
PointY *Z,*Y;
if(n<2)return false;
MergeSort(X,n);
Y=new PointY[n];
for(i=0;i<n;i++)
{
Y[i].p=i;
Y[i].x=X[i].x;
Y[i].y=X[i].y;
}
MergeSort(Y,n);
Z=new PointY[n];
closest(X,Y,Z,0,n-1,a,b,d);
delete []Y;
delete []Z;
return true;
}
void main(void)
{
PointX X[]={{1,0.3,0.5},{2,0.9,0.15},{3,0.4,0.1},{4,0.5,0.5},
{5,0.2,0.3},{6,0.2,0.2},{7,0.9,0.8},{8,0.85,0.2}};
PointX a,b;
float d;
int ok=false;
ok=Cpair2(X,8,a,b,d);
if (ok)
printf("a=%d,b=%d,dist=%f\n",a.ID,b.ID,d);
else
printf("False!\n");
getchar();
}
