最近点对的分治算法求解

//最近对：分治法
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
struct node{
          
   
    int x;
    int y;
};

bool compare1(node p1,node p2)
{
          
   
    return p1.x < p2.x;
}

bool compare2(node p1,node p2)
{
          
   
    return p1.y < p2.y;
}
//返回两点之间的距离。
double distance(node p1,node p2)
{
          
   
    return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));    
}
//获取最近点对
double partition(node p[],int left,int right)
{
          
   
    //如果只有两个或者3个就直接算出距离返回
    if(right - left == 1)
    {
          
   
        return distance(p[left],p[right]);
    }
    if(right - left == 2)
    {
          
   
        double d1 = distance(p[left],p[left+1]);
        double d2 = distance(p[left],p[right]);
        double d3 = distance(p[left+1],p[right]);
        d2 = min(d1,d2);
        d3 = min(d2,d3);
        return d3;
    }
    //当坐标多于两个的时候，将其分成两部分，依次运算。
	//中间点的下标
    int m = (left + right)/2;
    //点集P1最近对的距离
    double d1 = partition(p,left,m);
    //点集P2最近对的距离
    double d2 = partition(p,m+1,right);
    double d = min(d1,d2);
    int l=left,r=right;
    //筛选中间可能距离最小的坐标。排除x之差大于d的坐标。
    while(p[l].x<p[m].x-d && l<=right)
    {
          
   
        l++;
    }
    while(p[r].x>p[m].x+d && l<=left)
    {
          
   
        r--;
    }

    double d3;
    //将筛选后的坐标以y的大小进行排序。
    sort(p+l,p+r+1,compare2);
    for(int i=l;i<r;i++)
    {
          
   
        for(int j=i+1;j<r;j++)
        {
          
   
            //筛选中间可能距离最小的坐标。排除y之差大于d的坐标。
            if(p[j].y-p[i].y > d)
            {
          
   
                break;
            }
            else
            {
          
   
                d3 = distance(p[i],p[j]);
                if(d3 < d)
                {
          
   
                    d = d3;
                } 
            }
        }
    }
}

int main()
{
          
   
    node p[20]; 
    cout << "请输入点数：";
    int n;
    cin >> n;
    cout << "请输入坐标：" << endl;
    for(int i=0;i<n;i++)
    {
          
   
        cin >> p[i].x >> p[i].y;
    }
    //根据每个坐标的x排序。
    sort(p,p+n,compare1);
    double d = partition(p,1,n);
    cout << "最短距离为:" << d << endl;
    return 0;
}