设计求解平面最邻近点对算法 1)数据没有事先预排序,设计算法O(n(logn)2)。 2)数据事先预排序,设计算法O(nlogn) C++代码
时间: 2024-02-06 17:08:55 浏览: 25
1)算法步骤:
1. 将点按照横坐标排序
2. 对于每个点,只需要检查它后面的若干个点即可,因为前面的点已经被检查过了
3. 对于每个点i,设最近点对为(i,j),则j的横坐标必定大于i的横坐标,从i的下一个点开始枚举j,直到找到一个点k,使得k的横坐标减去i的横坐标大于当前最小距离d,则可以停止枚举j了
4. 在第3步中,对于每个点i,都用一个大小为7的桶来记录与i距离在[0,6d]之间的点,这样可以减少比较次数
5. 在第3步中,如果找到了更小的距离,则更新最小距离和最近点对
时间复杂度:O(n(logn)2)
C++代码:
```
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 100000;
const int MAXM = 8;
const double INF = 1e20;
struct Point {
double x, y;
bool operator < (const Point& p) const {
return x < p.x;
}
} p[MAXN+5];
double dist(const Point& a, const Point& b) {
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx*dx + dy*dy);
}
double minDist(int l, int r) {
if (l == r) return INF;
if (l+1 == r) return dist(p[l], p[r]);
int mid = (l+r) / 2;
double d = min(minDist(l, mid), minDist(mid+1, r));
int cnt = 0;
for (int i = l; i <= r; i++) {
if (fabs(p[i].x - p[mid].x) < d) {
cnt++;
}
}
static int bucket[MAXM+5];
fill(bucket, bucket+MAXM+1, 0);
for (int i = l; i <= r; i++) {
for (int j = max(0, bucket[int((p[i].y - p[mid].y) / d * MAXM) - 1]); j <= min(MAXM, bucket[int((p[i].y - p[mid].y) / d * MAXM) + 1]); j++) {
if (dist(p[i], p[mid+j-4]) < d) {
d = dist(p[i], p[mid+j-4]);
}
}
bucket[int((p[i].y - p[mid].y) / d * MAXM)]++;
}
return d;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> p[i].x >> p[i].y;
}
sort(p+1, p+n+1);
double ans = minDist(1, n);
printf("%.4f\n", ans);
return 0;
}
```
2)算法步骤:
1. 将点按照横坐标排序
2. 对于每个点i,只需要检查它后面的若干个点即可,因为前面的点已经被检查过了
3. 对于每个点i,设最近点对为(i,j),则j的横坐标必定大于i的横坐标,从i的下一个点开始枚举j,直到找到一个点k,使得k的横坐标减去i的横坐标大于当前最小距离d,则可以停止枚举j了
4. 在第3步中,对于每个点i,都用一个大小为7的桶来记录与i距离在[0,6d]之间的点,这样可以减少比较次数
5. 在第3步中,如果找到了更小的距离,则更新最小距离和最近点对
时间复杂度:O(nlogn)
C++代码:
```
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 100000;
const int MAXM = 8;
const double INF = 1e20;
struct Point {
double x, y;
bool operator < (const Point& p) const {
return x < p.x;
}
} p[MAXN+5];
double dist(const Point& a, const Point& b) {
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx*dx + dy*dy);
}
double minDist(int l, int r) {
if (l == r) return INF;
if (l+1 == r) return dist(p[l], p[r]);
int mid = (l+r) / 2;
double d = min(minDist(l, mid), minDist(mid+1, r));
static Point tmp[MAXN+5];
int cnt = 0;
for (int i = l; i <= r; i++) {
if (fabs(p[i].x - p[mid].x) < d) {
tmp[++cnt] = p[i];
}
}
sort(tmp+1, tmp+cnt+1, [](const Point& a, const Point& b) {
return a.y < b.y;
});
static int bucket[MAXM+5];
fill(bucket, bucket+MAXM+1, 0);
for (int i = 1; i <= cnt; i++) {
for (int j = max(0, bucket[int((tmp[i].y - tmp[1].y) / d * MAXM) - 1]); j <= min(MAXM, bucket[int((tmp[i].y - tmp[1].y) / d * MAXM) + 1]); j++) {
if (dist(tmp[i], tmp[1+j-4]) < d) {
d = dist(tmp[i], tmp[1+j-4]);
}
}
bucket[int((tmp[i].y - tmp[1].y) / d * MAXM)]++;
}
return d;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> p[i].x >> p[i].y;
}
sort(p+1, p+n+1);
double ans = minDist(1, n);
printf("%.4f\n", ans);
return 0;
}
```