分治法实现最近点对问题（C++）

最近点对问题

要求

• 随机生成30个浮点数（1-10）之间
• 求出最近距离的两点
• C语言实现

#include <iostream>
#include <math.h>

using namespace std;

struct dot{  //点结构
    float x;
    float y;
};
void sortByX(dot dots[6],int num){  //将点按照X坐标从小到大排列好(冒泡)
    for (int i = num-1; i >= 0; --i) {
        for (int j = 0; j < i; ++j) {
            if (dots[j].x > dots[j + 1].x) {
                dot flag = dots[j];
                dots[j] = dots[j + 1];
                dots[j + 1] = flag;

            }
        }
    }
}
void sortByY(dot dots[6],int num){  //将点按照Y坐标从小到大排列好(冒泡)
    for (int i = num-1; i >= 0; --i) {
        for (int j = 0; j < i; ++j) {
            if (dots[j].y > dots[j + 1].y) {
                dot flag = dots[j];
                dots[j] = dots[j + 1];
                dots[j + 1] = flag;

            }
        }
    }
}
float calculateMin(float min1,float min2){ //求最小值
    if(min1>=min2){
        return min2;
    }else{
        return min1;
    }
}
float calculateMin3(dot p1[30],int num1,dot p2[30],int num2,float min){
    float Min;
    for (int i = 0; i < num1; ++i) { //对p1内的每个点遍历
        float min2;
        for (int j = 0; j < num2; ++j) { //筛选出y-mim到y+min之内的
            if(p1[i].y-min<=p2[j].y&&p2[j].y<=p1[i].y+min&&p1[i].x!=p2[j].x&&p1[i].y!=p2[j].y){ //还要保证不是同一个点
                float length = sqrt(pow((p1[i].x-p2[j].x),2)+pow((p1[i].y-p2[j].y),2));//计算距离
                if(j==0){ //第一次的情况
                    min2 = length;
                }else{
                    if(length<min)
                        min2 = length;
                }
            }
        }
        if(i==0){
            Min=min;
        }else{
            if(min<Min)
                Min = min2;
        }
    }
    return Min;
}
int getP1(dot p1[30],dot dots[30],int head,int num,float min,int m){ //求出p1集合
    int j=0;
    for (int i = head; i < head+num; ++i) {
        if(dots[m].x-min<=dots[i].x&&dots[i].x<=dots[m].x){
            p1[j] = dots[i];
            j++;
        }
    }
    return j; //返回p1的元素个数
}
int getP2(dot p2[30],dot dots[30],int head,int num,float min,int m){ //求出p2集合
    int j=0;
    for (int i = head; i < head+num; ++i) {
        if(dots[m].x<=dots[i].x&&dots[i].x<=dots[m].x+min){
            p2[j] = dots[i];
            j++;
        }
    }
    return j; //返回p2的元素个数
}
float calculate(dot dots[6],int head,int num){ //head为起始下标，num为点的个数
    if(num==2){
        float min =  sqrt(pow((dots[head].x-dots[head+1].x),2)+pow((dots[head].y-dots[head+1].y),2));
        return min;
    }else{
        int m = (2*head+num-1)/2; //求出中位数下标
        float min1 = calculate(dots,head,m-head+1); //求出左侧最小值
        float min2 = calculate(dots,m,head+num-m); //求出右侧最小值
        float min = calculateMin(min1,min2); //求出两者的最小值
        dot p1[30];
        int num1 = getP1(p1,dots,head,num,min,m);//求出p1集合
        dot p2[30];
        int num2 = getP2(p2,dots,head,num,min,m);//求出p2集合
        sortByY(p1,num1); //p1按Y排序
        sortByY(p2,num2);//p2按Y排序
        float min3 = calculateMin3(p1,num1,p2,num2,min); //通过p1与p2求出最小值
        return calculateMin(min,min3);
    }
}
int main(void) {
    dot dots[30];
    cout<<"随机生成30个点（float）"<<endl;
    for (int i = 0; i < 30; ++i) { //随机生成30个浮点数字
        dots[i].x = 1+1.0*rand()/RAND_MAX *(10-1);
    }
    for (int i = 0; i < 30; ++i) { //随机生成30个浮点数字
        dots[i].y = 1+1.0*rand()/RAND_MAX *(10-1);
    }
    for (int i = 0; i < 30; ++i) {
        cout<<"第"<<i+1<<"个点："<<"("<<dots[i].x<<","<<dots[i].y<<")"<<endl;
        cout<<"==================="<<endl;
    }
    sortByX(dots,7); //先按x大小排序
    float d = calculate(dots, 0, 7);
    cout<<"最短距离是"<<d<<endl;


}