clostest_pair.cpp

最近点对算法的实现

/*设计题目：最近点对问题*/

//输入:平面上的n个点的集合S
//输出:S中两个点的最小距离
#include<iostream>
#include<cmath>
#include<cstdlib>
using namespace std;
#define MaxN 20
#define debug 0
typedef struct point
{ //定义点的结构类型
    double x,y;
}point;   
void Queuesortx(point* A,int low,int high)
{
    double tempx,tempy;
    int i=low,j=high;
    if(low<high)
    {
        tempx=A[i].x;
        tempy=A[i].y;
        while(i!=j)
        {
            while(j>i && A[j].x>tempx) j--;
            if(i<j)
            {
                A[i].x=A[j].x;
                A[i].y=A[j].y;
                i++;
            }
            while(i<j && A[i].x<tempx) i++;
            if(i<j)
            {
                A[j].x=A[i].x;
                A[j].y=A[i].y;
                j--;
            }
            A[i].x=tempx;
            A[i].y=tempy;
            Queuesortx(A,low,i-1);
            Queuesortx(A,i+1,high);
        }
    }                  
}
void Queuesorty(point* A,int low,int high)
{
    double tempx,tempy;
    int i=low,j=high;
    if(low<high)
    {
        tempx=A[i].x;
        tempy=A[i].y;
        while(i!=j)
        {
            while(j>i && A[j].y>tempy) j--;
            if(i<j)
            {
                A[i].x=A[j].x;
                A[i].y=A[j].y;
                i++;
            }
            while(i<j && A[i].y<tempy) i++;
            if(i<j)
            {
                A[j].x=A[i].x;
                A[j].y=A[i].y;
                j--;
            }
            A[i].x=tempx;
            A[i].y=tempy;
            Queuesorty(A,low,i-1);
            Queuesorty(A,i+1,high);
        }
    }                  
}
//求两点间的距离
double d(point p1,point p2)
{
    double dx,dy,d;
    dx=p1.x-p2.x;
    dy=p1.y-p2.y;
    d=pow(dx,2)+pow(dy,2);
    return sqrt(d);
}   
void printarry(point* points,int n)
{   //输出点集  test
    for(int i=0;i<n;i++)
    {  
           cout<<"("<<points[i].x<<","<<points[i].y<<") ";
    }
    cout<<endl;
}
double cp(point *S,point *Y,int low,int high)
{
    double min;
    int n=high-low+1; //点的个数
   
    //点的个数小于三个,则直接计算
    if(n<=1) return 65536;
    if(n==2) return d(S[low],S[high]);
    if(n==3){
        double d1,d2,d3;
        d1=d(S[low],S[low+1]);
        d2=d(S[low],S[low+2]);
        d3=d(S[low+1],S[low+2]);
        if(d1<=d2) min=d1;
        else min=d2;
        if(min>d3) min=d3;
    }
      
    //分治
    int mid;
    double x0,minl,minr;
   
    mid = (low+high)/2;
    x0 = S[mid].x;
    minl = cp(S,Y,low,mid);
    minr = cp(S,Y,mid+1,high);
    if(minl<=minr) min = minl;
    else min = minr;
   
    int i,k=0;
	point* T=(point *)malloc(sizeof(point)*n);
    //point T[n];
    for(i=0;i<n;i++) //从Y中取T
    {
        if(fabs(Y[i].x-x0)<=min)
        {
            T[k].x=Y[i].x;
            T[k].y=Y[i].y;
            k++;
        }
    }
   
    double minlr=2*min;
    for(i=0;i<k;i++)
    {
        int jj;
        if((i+7)<k) jj=i+7;
        else jj=k;       
        for(int j=i+1;j<jj;j++)
        {
            double dd=d(T[i],T[j]);
            if(dd<minlr) minlr = dd;
        }
    }          
   
    if(minlr < min) min=minlr;
   
    return min; 
}       
 
int main()
{   
    int n,i;                  //定义点的个数   
    cout<<"请输入你要输入的点的个数:"; 
    cin>>n;
	point* S=(point *)malloc(sizeof(point)*n);
    //point S[n];            //定义点集
    cout<<"请输入点坐标（x，y）:\n";
    for(i=0;i<n;i++)
    {
        cin>>S[i].x>>S[i].y;
    }   
  
   
    //以x坐标增序对S中的点排序
     Queuesortx(S,0,n-1);    
    
     //以x坐标增序对S中的点排序 -> Y[]
	point* Y=(point *)malloc(sizeof(point)*n);
     //point Y[n];
     for(i=0;i<n;i++)
     {
         Y[i].x=S[i].x;
         Y[i].y=S[i].y;
     }    
     Queuesorty(Y,0,n-1);
    
     //test
     if(debug) printarry(S,n);
     if(debug) printarry(Y,n);
    
     //cp(1,n) -> min
     double min=cp(S,Y,0,n-1);
    
     cout<<"最近的两点间的距离为:"<<min<<endl;
           
    system("pause");
    return 0;
}