在一个集合中有n个点，找出这n个点中最短的两个点的位置，并输出这个位置：
#include <iostream>
#include <cmath>
using namespace std;
class PointX{
public:
double x;
double y;
};
class PointY{
public:
double x;
double y;
int p;
};
//考虑使用运算符重载，与类内部写一个比较函数功能相似
void sortPointX(PointX X[],int len){
PointX temp;
for(int i=len;i>0;--i){//有len个元素进行len-1次比较
for(int j=0;j<i-1;++j){
if(X[j].x>X[j+1].x){
temp = X[j+1];
X[j+1]=X[j];
X[j]=temp;
}
}
}
}
void sortPointY(PointY Y[],int len){
PointY temp;
for(int i=len;i>0;--i){//表示有多少个元素进行比较
for(int j=0;j<i-1;++j){
if(Y[j].y>Y[j+1].y){
temp = Y[j+1];
Y[j+1]=Y[j];
Y[j]=temp;
}
}
}
}
//两点之间的距离
template <class Type>
inline double dist(const Type& u, const Type& v){
double dx=u.x-v.x;
double dy=u.y-v.y;
return sqrt(dx*dx+dy*dy);
}
void mergeY(PointY Z[],PointY Y[],int l,int m,int r){
int i=l;
int j=m+1;
int k=l;
while(i<=m-1&&j<=r)
{
if(Z[i].y<Z[j].y){
Y[k++]=Z[i++];
}else{
Y[k++]=Z[j++];
}
}
while(i<=m-1){
Y[k++]=Z[i++];
}
while(j<=r){
Y[k++]=Z[j++];
}
}
//求最短距离
void closest(PointX X[],PointY Y[],PointY Z[],int l,int r,PointX &a,PointX& b,double& d){
cout<<l<<" "<<r<<endl;
cout<<"hello closest"<<endl;
if(r<l){
cout<<"l:"<<l<<" r: "<<r<<endl;
return;
}
if(r-l==0)return;
if(r-l==1){
a=X[l];
b=X[r];
d=dist(a,b);
return;
}
if(r-l==2){
double d1=dist(X[l],X[l+1]);
double d2=dist(X[l+1],X[r]);
double d3=dist(X[l],X[r]);
if(d1<d2&&d1<d3){
a=X[l];
b=X[l+1];
d=d1;
return;
}
if(d2<d3){
a=X[l+1];
b=X[r];
d=dist(X[l+1],X[r]);
}else{
a=X[l];
b=X[r];
d=dist(X[l],X[r]);
}
return;
}
//多于三点的情形，分治法
int mid = (l+r)/2;
int f=l;
int g=mid+1;
for(int i=l;i<=r;++i){
if(Y[i].p>mid){
Z[g++]=Y[i];
}
else {
Z[f++]=Y[i];
}
}
closest(X,Z,Y,l,mid,a,b,d);
double dr;
PointX ar;
PointX br;
closest(X,Z,Y,mid+1,r,ar,br,dr);
if(dr<d){
a=ar;
b=br;
d=dr;
}
// for(int i=l;i<=r;++i)
// {
// cout<<i<<" "<<Y[i].x<<" "<<Y[i].y<<endl;
// }
//重构数组Y
mergeY(Z,Y,l,mid,r);//我不懂为什么要重构数组Y
//把符合条件的点放到Z中
int k=l;
for(int i=l;i<=r;++i){
if(fabs(Y[i].x-Y[mid].x)<d){
Z[k++]=Y[i];
}
}
//搜索Z[1:k-1]
for(int i=l;i<k;++i){
for(int j=i+1;j<k&&(Z[j].y-Z[i].y)<d;++j){
double tem = dist(Z[j],Z[i]);
if(tem<d){
a=X[Z[i].p];
cout<<a.x<<" () "<<a.y<<endl;
cout<<Z[i].x<<" () "<<Z[i].y<<endl;
b=X[Z[j].p];
d=tem;
}
}
}
}
int main()
{
// void sortPointX(PointX X[],int len);
// void sortPointY(PointY Y[],int len);
// void closest(PointX X[],PointY Y[],PointY Z[],int a,int b,double d);
cout << "Hello world!" << endl;
time_t ti = time(NULL);
cout<<ti<<endl;
freopen("aaa.txt","r",stdin);
PointX a,b;
double d;
PointX X[101];
PointY Y[101];
PointY Z[101];
int len;
cin>>len;
for(int i = 0;i<len;++i){
cin>>X[i].x>>X[i].y;
}
sortPointX(X,len);
for(int i=0;i<len;++i){
Y[i].x=X[i].x;
Y[i].y=X[i].y;
Y[i].p=i;
}
sortPointY(Y,len);
closest(X,Y,Z,0,len-1,a,b,d);
cout<<"("<<a.x<<","<<a.y<<")"<<endl;
cout<<"("<<b.x<<","<<b.y<<")"<<endl;
cout<<"d: "<<d<<endl;
time_t endTime=time(NULL);
cout<<"所用时间："<<endTime-ti<<endl;
return 0;
}
在aaa.txt中为测试的数据，可以随便写的：
10
1 3
2 4
3 5
4 3
5 9
6 8
7 7
10 6
11 6
13 8
运行结果：
