给定n个点,求出其最近的两个点,要求打印输出两个点,屏幕输入点的个数以及点的坐标,用C++代码实现
时间: 2024-10-12 18:06:10 浏览: 24
蛮力法求解最近点对问题
在C++中,你可以使用优先队列(`std::priority_queue`)来解决这个问题。这是一个最小堆数据结构,每次添加元素都会保证顶部元素是最小的。我们可以维护两个堆,一个存放距离最远的点,另一个存放距离当前已知最近点的距离次远的点。
首先,假设每个点是一个结构体,包含一个整数ID和一对坐标。下面是基本的代码实现:
```cpp
#include <iostream>
#include <queue>
#include <vector>
struct Point {
int id;
int x, y; // 假设二维坐标
};
int distance(const Point& a, const Point& b) {
return std::sqrt(std::pow(a.x - b.x, 2) + std::pow(a.y - b.y, 2));
}
void findNearestPoints(int n, std::vector<Point>& points) {
if (n < 2) {
std::cerr << "Error: At least two points are required.\n";
return;
}
std::priority_queue<Point, std::vector<Point>, std::greater<Point>> minHeap; // 最近点
std::priority_queue<Point> secondMinHeap; // 次近点
// 初始化最小堆
for (const auto& point : points) {
minHeap.push(point);
}
Point nearest = minHeap.top(); // 当前最近点
minHeap.pop();
while (!minHeap.empty()) { // 遍历剩余点
Point next = minHeap.top();
minHeap.pop();
// 更新次近点
if (distance(nearest, next) > distance(nearest, secondMinHeap.top())) {
secondMinHeap.push(next);
}
// 如果新点更接近
if (distance(secondMinHeap.top(), nearest) > distance(next, nearest)) {
nearest = secondMinHeap.top();
secondMinHeap.pop();
minHeap.push(next); // 把更新后的次近点放回最小堆
}
}
std::cout << "The closest pair of points is (" << nearest.id << ", (" << nearest.x << ", " << nearest.y << ")) and (" << secondMinHeap.top().id << ", (" << secondMinHeap.top().x << ", " << secondMinHeap.top().y << "))\n";
}
int main() {
int n;
std::cout << "Enter the number of points: ";
std::cin >> n;
std::vector<Point> points(n);
for (int i = 0; i < n; ++i) {
std::cout << "Enter coordinates for point " << i+1 << ": ";
std::cin >> points[i].id >> points[i].x >> points[i].y;
}
findNearestPoints(n, points);
return 0;
}
```
这段代码首先获取用户输入的点的数量和坐标,然后计算并找到最近的两个点。注意,如果需要处理负数或非欧几里得距离,`distance`函数的实现可能会有所不同。
阅读全文