实验一最接近点对问题一、实验目的为进一步学习分治策略的基本思想，本次实验将通过求最接近点对问题来加深我们对分治策略的认识。
二、实验问题描述给定平面上N个点，找出其中的一对点，使得在n 个点组成的所有点对中，该点对间的距离最小。
三、设计思路及步骤将所给平面上n个点的集合S分成两个子集S1和S2，每个子集中约有n/2个点。
然后在每个子集中递归地求其最接近的点对。
先考虑一维的情形：设计一个求一维点集S的最接近点对的算法Bool Cpairl(S,d){N=|S|; if(n<2) {d=无穷大;return falSe;} m=S中各点坐标的中位数;构造S1和S2; //S1={x∈S|x<=m},S2={x∈S|x>m}Cpairl(S1,d1); Cpairl(S2,d2); p=max(S1); q=max(S2);D=min(d1,d2,q-p);return true;}由此推广到二维的情形：若矩形R中有多于6个S中的点，则由鸽舍原理易知，至少有一个（d/2）*（2d/3）的小矩形中有2个以上S中的点。
设u,v是位于同一小矩形中的2个点，则(x(u)-x(v))²+(y(u)-y(v))²<=(d/2)²+(2d/3)²=25d²/36因此distance（u,v）<=5d/6<d,与d的意义相矛盾。
四、算法实现代码//2d10-2 二维最邻近点对问题#include<time.h>#include<iostream>#include<cmath>using namespace std;const int M=50;//用类PointX和PointY表示依x坐标和y坐标排好序的点class PointX {public:int operator<=(PointX a)const{ return (x<=a.x); }int ID; //点编号float x,y; //点坐标};class PointY {public:int operator<=(PointY a)const{ return(y<=a.y); }int p; //同一点在数组x中的坐标float x,y; //点坐标};float Random();template <class Type>float dis(const Type&u,const Type&v);bool Cpair2(PointX X[], int n,PointX& a,PointX& b, float& d);void closest(PointX X[],PointY Y[],PointY Z[], int l, int r,PointX& a,PointX& b,float& d);template <typename Type>void Copy(Type a[],Type b[], int left,int right);template <class Type>void Merge(Type c[],Type d[],int l,int m,int r);template <class Type>void MergeSort(Type a[],Type b[],int left,int right);int main(){srand((unsigned)time(NULL));int length;cout<<"请输入点对数：";cin>>length;PointX X[M];cout<<"随机生成的二维点对为："<<endl;for(int i=0;i<length;i++){X[i].ID=i;X[i].x=Random();X[i].y=Random();cout<<"("<<X[i].x<<","<<X[i].y<<") ";}PointX a,b;float d;Cpair2(X,length,a,b,d);cout<<endl;cout<<"最邻近点对为：("<<a.x<<","<<a.y<<")和("<<b.x<<","<<b.y<<") "<<endl;cout<<"最邻近距离为： "<<d<<endl;return 0;}float Random(){float result=rand()%10000;return result*0.01;}//平面上任意两点u和v之间的距离可计算如下template <class Type>inline float dis(const Type& u,const Type& v){float dx=u.x-v.x;float dy=u.y-v.y;return sqrt(dx*dx+dy*dy);}bool Cpair2(PointX X[], int n,PointX& a,PointX& b,float& d){if(n<2) return false;PointX* tmpX = new PointX[n];MergeSort(X,tmpX,0,n-1);PointY* Y=new PointY[n];for(int i=0;i<n;i++) //将数组X中的点复制到数组Y中{Y[i].p=i;Y[i].x=X[i].x;Y[i].y=X[i].y;}PointY* tmpY = new PointY[n];MergeSort(Y,tmpY,0,n-1);PointY* Z=new PointY[n];closest(X,Y,Z,0,n-1,a,b,d);delete []Y;delete []Z;delete []tmpX;delete []tmpY;return true;}void closest(PointX X[],PointY Y[],PointY Z[], int l, int r,PointX& a,PointX& b,float& d){if(r-l==1) //两点的情形{a=X[l];b=X[r];d=dis(X[l],X[r]);return;}if(r-l==2) //3点的情形{float d1=dis(X[l],X[l+1]);float d2=dis(X[l+1],X[r]);float d3=dis(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=d2;}else {a=X[l];b=X[r];d=d3;}return;}//多于3点的情形，用分治法int m=(l+r)/2;int f=l,g=m+1;//在算法预处理阶段，将数组X中的点依x坐标排序，将数组Y中的点依y坐标排序//算法分割阶段，将子数组X[l:r]均匀划分成两个不想交的子集，取m=(l+r)/2//X[l:m]和X[m+1:r]就是满足要求的分割。
