平面最近点对问题，很基础的c++程序

Question

#include
#include
#include
#include
#include
#include
#include
#define LEFT_BOUND 0.0
#define RIGHT_BOUND 100.0
#define LOWER_BOUND 0.0
#define UPPER_BOUND 100.0
using namespace std;
struct Spot
{
float x;
float y;

Spot(float x, float y) : x(x), y(y) {};

};
typedef vector Spots;
inline bool xAxisCompare(const Spot& a, const Spot& b)
{
return a.x < b.x;
}
inline float calDist(const Spot& a, const Spot& b)
{
return sqrtf(powf(a.x - b.x, 2.0) + powf(a.y - b.y, 2.0));
}
float bruteForce(const Spots& sortedSpots, size_t left1, size_t right1, size_t left2, size_t right2)
{
float minDist = numeric_limits::max();
for (size_t i = left1; i <= right1; i++)
{
for (size_t j = left2; j <= right2; j++)
{
const float dist = calDist(sortedSpots[i], sortedSpots[j]);
if (dist < minDist)
{
minDist = dist;
}
}
}
return minDist;
}
float getMinDist(const Spots& sortedSpots, size_t left, size_t right)
{
if (left == right)
{
return numeric_limits::max();
}
if (left + 1 == right)
{
return calDist(sortedSpots[left], sortedSpots[right]);
}
const size_t leftRight = (left + right) / 2, rightLeft = leftRight + 1;
const float leftMin = getMinDist(sortedSpots, left, leftRight), rightMin = getMinDist(sortedSpots, rightLeft, right);
const float smallerOne = min(leftMin, rightMin);
if (sortedSpots[rightLeft].x - sortedSpots[leftRight].x >= smallerOne)
{
return smallerOne;
}
const float midBound = (sortedSpots[leftRight].x + sortedSpots[rightLeft].x) / 2.0;
const float leftBound = midBound - smallerOne, rightBound = midBound + smallerOne;
size_t i = leftRight, j = rightLeft;
while (i > left && sortedSpots[i - 1].x > leftBound)
{
i--;
}
while (j < right && sortedSpots[j + 1].x < rightBound)
{
j++;
}
return min(smallerOne, bruteForce(sortedSpots, i, leftRight, rightLeft, j));
}
float getMinDist(const Spots& spots)
{
const size_t num = spots.size();
if (num == 0)
{
return numeric_limits::max();
}
auto sortedSpots = spots;
sort(sortedSpots.begin(), sortedSpots.end(), xAxisCompare);
const size_t left = 0, right = num - 1;
return getMinDist(sortedSpots, left, right);
}

int main(int argc, char* argv[])
{
Spots spots;
srand(time(nullptr));
cout << "30 spots" << endl;
for (size_t i = 0; i < 30; i++)
{
const float x = LEFT_BOUND + (float)rand() / (float)RAND_MAX * (RIGHT_BOUND - LEFT_BOUND);
const float y = LOWER_BOUND + (float)rand() / (float)(RAND_MAX) * (UPPER_BOUND - LOWER_BOUND);
spots.emplace_back(x, y);
cout << '(' << x << ", " << y << ')' << endl;
}
cout << getMinDist(spots) << endl;
return 0;
}
问：const float x = LEFT_BOUND + (float)rand() / (float)RAND_MAX * (RIGHT_BOUND - LEFT_BOUND);这个函数什么意思
问：float getMinDist(const Spots& sortedSpots, size_t left, size_t right)
{
if (left == right)
{
return numeric_limits::max();
}
if (left + 1 == right)
{
return calDist(sortedSpots[left], sortedSpots[right]);
}
const size_t leftRight = (left + right) / 2, rightLeft = leftRight + 1;
const float leftMin = getMinDist(sortedSpots, left, leftRight), rightMin = getMinDist(sortedSpots, rightLeft, right);
const float smallerOne = min(leftMin, rightMin);
if (sortedSpots[rightLeft].x - sortedSpots[leftRight].x >= smallerOne)
{
return smallerOne;
}
const float midBound = (sortedSpots[leftRight].x + sortedSpots[rightLeft].x) / 2.0;
const float leftBound = midBound - smallerOne, rightBound = midBound + smallerOne;
size_t i = leftRight, j = rightLeft;
while (i > left && sortedSpots[i - 1].x > leftBound)
{
i--;
}
while (j < right && sortedSpots[j + 1].x < rightBound)
{
j++;
}
return min(smallerOne, bruteForce(sortedSpots, i, leftRight, rightLeft, j));
}
float getMinDist(const Spots& spots)
{
const size_t num = spots.size();
if (num == 0)
{
return numeric_limits::max();
}
auto sortedSpots = spots;
sort(sortedSpots.begin(), sortedSpots.end(), xAxisCompare);
const size_t left = 0, right = num - 1;
return getMinDist(sortedSpots, left, right);
}这个函数是什么意思
尤其是这个if (left == right)
{
return numeric_limits::max();
}
if (left + 1 == right)
{
return calDist(sortedSpots[left], sortedSpots[right]);
}
希望能讲得详细点

Answer 1

这是整理后的代码，加了很详细的注释，望采纳。

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <limits>
#include <ctime>
#include <cmath>
#include <cstddef>
using namespace std;

// 平面的边界
#define LEFT_BOUND 0.0
#define RIGHT_BOUND 100.0
#define LOWER_BOUND 0.0
#define UPPER_BOUND 100.0

// 定义了存储点的结构体,并定义了借助vector存储点集合的类型Spots
struct Spot
{
    float x;
    float y;
    Spot(float x, float y) : x(x), y(y){};
};
typedef vector<struct Spot> Spots;

float bruteForce(const Spots &sortedSpots, size_t left1, size_t right1, size_t left2, size_t right2);
float getMinDist(const Spots &sortedSpots, size_t left, size_t right);
float getMinDist(const Spots &spots);

// 对点集排序的具体规则
inline bool xAxisCompare(const Spot &a, const Spot &b) { return a.x < b.x;}

// 计算两点间距离
inline float calDist(const Spot &a, const Spot &b) { return sqrtf(powf(a.x - b.x, 2.0) + powf(a.y - b.y, 2.0));}

int main(int argc, char *argv[])
{
    Spots spots;    // 存储用到的点
    srand(time(nullptr));
    cout << "30 spots" << endl;

    // 随机初始化点的坐标,并输出生成点的具体值
    for (size_t i = 0; i < 30; i++)
    {
        // 随机生成x, y的坐标
        /*
            rand() :An integer value between 0 and RAND_MAX.生成一个0到RAND_MAX范围内的随机数
            (float)rand() / (float)RAND_MAX: 生成0~1之间的随机数
            (float)rand() / (float)RAND_MAX * (RIGHT_BOUND - LEFT_BOUND): 生成边界范围内的随机数
            LEFT_BOUND + (float)rand() / (float)RAND_MAX * (RIGHT_BOUND - LEFT_BOUND): 将生成的数加上左边界的值成为合法的点坐标
        */
        const float x = LEFT_BOUND + (float)rand() / (float)RAND_MAX * (RIGHT_BOUND - LEFT_BOUND);
        const float y = LOWER_BOUND + (float)rand() / (float)(RAND_MAX) * (UPPER_BOUND - LOWER_BOUND);
        
        // 将点放入点集并输出该点
        spots.emplace_back(x, y);
        cout << '(' << x << ", " << y << ')' << endl;
    }

    // 输出平面内最近的点
    cout << getMinDist(spots) << endl;

    return 0;
}

float bruteForce(const Spots &sortedSpots, size_t left1, size_t right1, size_t left2, size_t right2)
{
    float minDist = numeric_limits<float>::max();
    for (size_t i = left1; i <= right1; i++)
    {
        for (size_t j = left2; j <= right2; j++)
        {
            const float dist = calDist(sortedSpots[i], sortedSpots[j]);
            if (dist < minDist)
            {
                minDist = dist;
            }
        }
    }
    return minDist;
}

// 将排序好的点集与边界值进一步计算得出最小距离
float getMinDist(const Spots &sortedSpots, size_t left, size_t right)
{
    // 点集的左右边界相同，即点集中没有元素，返回一个最大值作为异常情况的标识
    if (left == right)
    {
        return numeric_limits<float>::max();
    }

    // 如果只存在两个点，距离就是这两点之间的距离
    if (left + 1 == right)
    {
        return calDist(sortedSpots[left], sortedSpots[right]);
    }

    // 二分的两个区间的中间的边界值
    const size_t leftRight = (left + right) / 2, rightLeft = leftRight + 1;

    // 二分的左右边界的距离最小值
    const float leftMin = getMinDist(sortedSpots, left, leftRight);
    const float rightMin = getMinDist(sortedSpots, rightLeft, right);

    // 左右边界最小值中更小的那一个
    const float smallerOne = min(leftMin, rightMin);

    
    if (sortedSpots[rightLeft].x - sortedSpots[leftRight].x >= smallerOne)
    {
        return smallerOne;
    }
    const float midBound = (sortedSpots[leftRight].x + sortedSpots[rightLeft].x) / 2.0;
    const float leftBound = midBound - smallerOne, rightBound = midBound + smallerOne;
    size_t i = leftRight, j = rightLeft;
    while (i > left && sortedSpots[i - 1].x > leftBound)
    {
        i--;
    }
    while (j < right && sortedSpots[j + 1].x < rightBound)
    {
        j++;
    }
    return min(smallerOne, bruteForce(sortedSpots, i, leftRight, rightLeft, j));
}

// 给定一个点集，输出点集内各点之间的最短距离
float getMinDist(const Spots &spots)
{
    const size_t num = spots.size();    // 存储点集中点的个数
    if (num == 0)
    {
        return numeric_limits<float>::max();
    }

    // 将点集拷贝,可改写为Spots sortedSpots = spots;
    auto sortedSpots = spots;

    // 按点的横坐标对点排序
    sort(sortedSpots.begin(), sortedSpots.end(), xAxisCompare);

    // 点集的左右边界
    const size_t left = 0, right = num - 1;
    // 将排序好的点集与边界值进一步计算得出最小距离
    return getMinDist(sortedSpots, left, right);
}