最近对问题_最近对问题输入什么

问题：最近对问题

/*

第一种方法：蛮力法解决的最近对问题

*/

C++代码如下：

#include<iostream>
 
using namespace std;
 
#define N 1005
 
int x[N],y[N];
 
int ClosestPoints(int x[],int y[],int n)
 
{
 
    int index1,index2;//记录点对
 
    int d,minDist = 1000000;//假设最大距离不超过1000000
 
    for(int i=0;i<n-1;i++)
 
        for(int j=i+1;j<n;j++)
 
    {
 
        d=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
 
        if(d<minDist)
 
        {
 
            minDist = d;
 
            index1=i+1;
 
            index2=j+1;
 
        }
 
    }
 
    cout<<"最近对的点对是： "<<index1<<"  and   "<<index2<<endl;
 
           cout<<"最近对的距离是：";
 
    return minDist;
 
}
 
 
int main()
 
{
 
    int n;
 
    cout<<"请输入点的对数：　";
 
    cin>>n;
 
    cout<<"请依次输入(x,y)的值： "<<endl;
 
    for(int i=0;i<n;i++)
 
        cin>>x[i]>>y[i];
 
 
    cout<<ClosestPoints(x,y,n);
 
    return 0;
 
}

运行截图如下：

第二种方法：分治法解决

分析：用分治法解决最近对问题，很自然的想法就是将集合S分成两个子集 S_{1}和 S_{2}，每个子集中有n/2个点。然后在每个子集中递归地求其最接近的点对，在求出每个子集的最接近点对后，在合并步中，如果集合 S 中最接近的两个点都在子集 S_{1}或 S_{2}中，则问题很容易解决，如果这两个点分别在 S_{1}和 S_{2}中，问题就比较复杂了。

伪代码：

C++代码如下：

#include <iostream>
 
#include <math.h>
 
using namespace std;
 
 
const int n = 8;
 
 
//定义结构体表示集合S中的 点的坐标
 
struct point{
 
       int x, y;
 
};
 
 
double Closest(point S[], int low, int high);       //实现求最近对距离
 
double Distance(point a, point b);                                  //求两点之间距离
 
int Partition(point r[], int first, int end);             //划分【课本P62】
 
void QuickSort(point r[], int first, int end);         //快速排序【课本P63】
 
 
//实现求最近对距离
 
double Closest(point S[], int low, int high){
 
       double d1, d2, d3, d;
 
       int mid, i, j, index;
 
       point P[n];                   //存放点集合 P1和P2
 
 
       //如果只有两个点，返回这两个点间的距离
 
       if (high - low == 1) {
 
              return Distance(S[low], S[high]);
 
       }
 
 
       //如果有三个点，求最近点对距离
 
       if (high - low == 2)      {
 
              d1 = Distance(S[low], S[low + 1]);
 
              d2 = Distance(S[low + 1], S[high]);
 
              d3 = Distance(S[low], S[high]);
 
              if ((d1 < d2) && (d1 < d3))  return d1;
 
              else if (d2 < d3) return d2;
 
              else return d3;
 
       }
 
 
       mid = (low + high) / 2;                      //计算中间点
 
       d1 = Closest(S, low, mid);                  //递归求解子问题①
 
       d2 = Closest(S, mid + 1, high);          //递归求解子问题②
 
 
       if (d1 <= d2) d = d1;                         //已下为求解子问题③
 
       else d = d2;
 
       index = 0;
 
       for (i = mid; (i >= low) && (S[mid].x - S[i].x < d); i--)                   //建立点集合P1
 
              P[index++] = S[i];
 
       for (i = mid + 1; (i <= high) && (S[i].x - S[mid].x < d); i++)           //建立点集合P2
 
              P[index++] = S[i];
 
 
       //对集合P1、P2按y坐标升序排列
 
       QuickSort(P, 0, index - 1);
 
 
       //依次处理集合P1和P2中的点
 
       for (i = 0; i < index; i++)      {
 
              for (j = i + 1; j < index; j++)        {
 
                     if (P[j].y - P[i].y >= d)           //超出y坐标的范围，点P[i]处理完毕
 
                            break;
 
                     else               {
 
                            d3 = Distance(P[i], P[j]);
 
                            if (d3 < d)
 
                                   d = d3;
 
                     }
 
              }
 
       }
 
       return d;
 
}
 
 
//求两点之间距离
 
double Distance(point a, point b){
 
       return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
 
}
 
 
int Partition(point r[], int first, int end){                           //划分
 
       int i = first, j = end;                                                              //初始化待划分区间
 
       while (i < j)    {
 
              while (i < j && r[i].y <= r[j].y) j--;                            //右侧扫描
 
              if (i < j) {
 
                     point temp = r[i]; r[i] = r[j]; r[j] = temp;     //将较小记录交换到前面
 
                     i++;
 
              }
 
              while (i < j && r[i].y <= r[j].y) i++;                          //左侧扫描
 
              if (i < j) {
 
                     point temp = r[i]; r[i] = r[j]; r[j] = temp;    //将较大记录交换到后面
 
                     j--;
 
              }
 
       }
 
       return i;                                                                               // 返回轴值记录的位置
 
}
 
 
void QuickSort(point r[], int first, int end){  //快速排序
 
       int pivot;
 
       if (first < end) {
 
              pivot = Partition(r, first, end);             //划分，pivot是轴值在序列中的位置
 
              QuickSort(r, first, pivot - 1);               //求解子问题1，对左侧子序列进行快速排序
 
              QuickSort(r, pivot + 1, end);              //求解子问题2，对右侧子序列进行快速排序
 
       }
 
}
 
 
 
int main()
 
{
 
       //输入按x坐标升序排列的n个点的集合
 
       point S[n] = { {1,4},{1,8},{2,1},{3,2},{4,4},{5,1},{6,6},{7,2} };
 
       double minDist = Closest(S, 0, n - 1);
 
       //输出最近点对的距离
 
       cout << "最近点对距离为："<< minDist << endl;
 
       return 0;
 
}

运行截图如下：

时间复杂度：T(n)=O(nlog2n)