设 p1 = ( x1 , y1 ) , p2 = ( x2 , y2 ) , ⋯ , pn = ( xn , yn ) 是平面上 n 个点构成的集合 S , 设计算 法找出集合 S 中距离最近的点对。 蛮力法
-
初始化最小距离：首先，将最小距离
minDist初始化为正无穷大（+∞），表示当前还没有找到任何点对。 -
双重循环遍历所有点对：使用两个嵌套的循环遍历集合 S 中的所有点对 (pi,pj)，其中 i<j。
-
计算距离：对于每一对点 (pi,pj)，计算其欧几里得距离的平方 d=(xi−xj)2+(yi−yj)2。注意，这里直接计算平方，避免了开平方根的操作，因为平方根函数是单调增函数，不影响比较结果。
-
更新最小距离：如果当前点对的距离平方 d 小于
minDist，则更新minDist为 d，并记录这对点的索引index1和index2。 -
返回最小距离：循环结束后，返回最小距离
minDist。
#include <iostream>
#include <vector>
#include <cmath> // 实际上在这个程序中未直接使用，但通常用于数学运算
#include <limits.h> // 包含 INT_MAX 的定义
using namespace std;
// 函数声明
int ClosestPoints(int n, const int x[], const int y[], int& index1, int& index2);
int main() {
int n; // 点的数量
cout << "请输入点的数量: ";
cin >> n;
vector<int> x_coords(n), y_coords(n); // 使用vector存储坐标
cout << "请输入各点的x坐标和y坐标（每输入一个坐标后按回车，依次输入所有点的坐标）:\n";
for (int i = 0; i < n; ++i) {
cin >> x_coords[i];
cin >> y_coords[i];
}
int index1, index2; // 存储最近点对的索引
int minDistSquared = ClosestPoints(n, x_coords.data(), y_coords.data(), index1, index2);
// 输出最近点对的坐标和它们之间的实际距离
cout << "距离最近的点对是: (" << x_coords[index1] << ", " << y_coords[index1] << ") 和 (" << x_coords[index2] << ", " << y_coords[index2] << ")\n";
cout << "它们之间的距离是: " << sqrt(minDistSquared) << "\n";
return 0;
}
// 函数定义
int ClosestPoints(int n, const int x[], const int y[], int& index1, int& index2) {
int minDistSquared = INT_MAX; // 使用 INT_MAX 初始化最小距离的平方为最大整数
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int d_squared = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
if (d_squared < minDistSquared) {
minDistSquared = d_squared;
index1 = i;
index2 = j;
}
}
}
return minDistSquared; // 返回最小距离的平方
}分治法
- 定义点结构体：
struct Point { int x, y; };定义了一个表示二维点的结构体，包含两个整数成员变量x和y，分别表示点的横坐标和纵坐标。
- 比较函数：
bool compareX(const Point& a, const Point& b)是一个用于按x坐标排序点的比较函数。
- 辅助函数：
int stripClosest(const vector<Point>& strip, int d)是一个在条带内查找最近对的辅助函数。它接受一个按y坐标排序的点集strip和一个距离d，然后返回条带内点对的最近距离。这个函数使用蛮力法（即嵌套循环）来比较条带内所有点对之间的距离。
- 分治函数：
int closestPoints(const std::vector<Point>& S)是实现分治算法的主函数。它接受一个点集S，并返回点集中距离最近的点对的距离的平方（为了避免开方运算，提高效率）。- 函数首先检查点集的大小。如果小于 2，则返回无穷大（在这里用
INT_MAX表示）。 - 然后，它复制点集并按
x坐标排序。 - 接着，找到中位数点，并根据中位数将点集分成两部分：
S1和S2。 - 对
S1和S2递归调用closestPoints函数，得到它们内部的最近距离d1和d2。 - 然后，计算
d为d1和d2中的较小值。 - 接下来，构造一个条带
P，包含与中位数x坐标距离小于d的所有点。 - 在条带
P内调用辅助函数stripClosest来查找最小距离dPrime。 - 最后，返回
d和dPrime中的较小值作为全局最小距离的平方。
- 主函数：
int main()函数中创建了一个示例点集，并调用closestPoints函数来计算最近点对的距离。然后，它计算距离的平方根并输出结果。
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits> // 用于定义足够大的数来表示无穷大
#include<iostream>
using namespace std;
// 定义点的结构体
struct Point {
int x, y;
};
// 比较函数，用于按x坐标排序点
bool compareX(const Point& a, const Point& b) {
return a.x < b.x;
}
// 辅助函数，用于在条带内查找最近对
int stripClosest(const vector<Point>& strip, int d) {
int minDist = d; // 初始化最小距离为当前已知的最小距离d
vector<Point> sortedStrip(strip); // 复制条带并按y坐标排序
sort(sortedStrip.begin(), sortedStrip.end(), [](const Point& a, const Point& b) { return a.y < b.y; });
// 在排序后的条带内使用蛮力法查找最小距离
for (size_t i = 0; i < sortedStrip.size(); ++i) {
for (size_t j = i + 1; j < sortedStrip.size() && (sortedStrip[j].y - sortedStrip[i].y) < minDist; ++j) {
int dist = (sortedStrip[i].x - sortedStrip[j].x) * (sortedStrip[i].x - sortedStrip[j].x) +
(sortedStrip[i].y - sortedStrip[j].y) * (sortedStrip[i].y - sortedStrip[j].y);
if (dist < minDist) {
minDist = dist;
}
}
}
return minDist;
}
// 分治法解决最近对问题
int closestPoints(const std::vector<Point>& S) {
int n = S.size();
if (n < 2) {
// 如果点的数量小于2，则没有最近对，可以返回一个表示无穷大的数
return INT_MAX; // 或者其他足够大的数
}
// 按x坐标排序点集
vector<Point> sortedS(S);
sort(sortedS.begin(), sortedS.end(), compareX);
// 找到中位数（这里使用中位数点的x坐标值）
int mIndex = n / 2;
Point median = sortedS[mIndex];
// 分割点集为S1和S2
vector<Point> S1, S2;
for (int i = 0; i < n; ++i) {
if (i < mIndex) {
S1.push_back(sortedS[i]);
}
else if (i > mIndex) { // 跳过中位数
S2.push_back(sortedS[i]);
}
}
// 递归求解S1和S2中的最近对距离
int d1 = closestPoints(S1);
int d2 = closestPoints(S2);
int d = std::min(d1, d2);
// 构造条带P，包含S1和S2中与中位数m的x坐标距离小于d的点
vector<Point> P;
for (const auto& point : sortedS) {
if (abs(point.x - median.x) < d) {
P.push_back(point);
}
}
// 在条带P内使用辅助函数查找最小距离
int dPrime = stripClosest(P, d);
// 返回全局最小距离
return min(d, dPrime);
}
int main() {
// 示例点集（需要用户输入或硬编码）
vector<Point> points = { {0, 0}, {1, 1}, {2, 2}, {20, 20}, {21, 21}, {10, 15} }; // 用实际的点初始化
// 调用函数并输出结果
int minDistSquared = closestPoints(points);
double minDist = sqrt(minDistSquared);
cout << "最近点对的距离是: " << minDist << endl;
return 0;
}