数据没有事先预排序设计求解平面最邻近点对算法

对于平面最邻近点对问题，一种经典的解法是分治法，其时间复杂度为 O(nlogn)。具体实现思路为：

1. 将所有点按照 x 坐标从小到大排序。

2. 在排序后的点集中，找到中间的那个点 mid，并将点集分成两半。

3. 递归地在左右两半中分别寻找最邻近点对。

4. 然后将左右两半中的最小距离 min_dist 取出来。

5. 最后需要考虑跨越两个子集的点对，也就是横跨左右两半的点对。对于这些点对，我们只需要考虑 x 坐标在 [mid - min_dist, mid + min_dist] 范围内的点，然后按照 y 坐标从小到大排序，依次判断相邻的点对之间的距离，更新最小距离即可。

需要注意的是，这种算法没有使用数据预排序的技巧，而是在运行过程中进行了一次排序。虽然这样会增加算法的时间复杂度，但是仍然能够在合理的时间内求解平面最邻近点对问题。

相关问题

数据没有事先预排序设计求解平面最邻近点对算法c语言

以下是使用分治法求解平面最邻近点对问题的 C 语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAXN 10000

struct Point {
    double x, y;
};

int cmp_x(const void *a, const void *b) {
    struct Point *p1 = (struct Point *)a;
    struct Point *p2 = (struct Point *)b;
    return (p1->x < p2->x) ? -1 : 1;
}

int cmp_y(const void *a, const void *b) {
    struct Point *p1 = (struct Point *)a;
    struct Point *p2 = (struct Point *)b;
    return (p1->y < p2->y) ? -1 : 1;
}

double dist(struct Point p1, struct Point p2) {
    double dx = p1.x - p2.x;
    double dy = p1.y - p2.y;
    return sqrt(dx*dx + dy*dy);
}

double min_dist(struct Point *a, int n) {
    if (n <= 1) return 1e9;
    if (n == 2) return dist(a[0], a[1]);

    int mid = n / 2;
    double midx = a[mid].x;

    double d1 = min_dist(a, mid);
    double d2 = min_dist(a + mid, n - mid);
    double d = fmin(d1, d2);

    struct Point *b = (struct Point *)malloc(n * sizeof(struct Point));
    int m = 0;
    for (int i = 0; i < n; i++) {
        if (fabs(a[i].x - midx) < d) {
            b[m++] = a[i];
        }
    }

    qsort(b, m, sizeof(struct Point), cmp_y);
    for (int i = 0; i < m; i++) {
        for (int j = i + 1; j < m && b[j].y - b[i].y < d; j++) {
            double d3 = dist(b[i], b[j]);
            if (d3 < d) d = d3;
        }
    }

    free(b);
    return d;
}

int main() {
    int n;
    struct Point a[MAXN];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lf%lf", &a[i].x, &a[i].y);
    }

    qsort(a, n, sizeof(struct Point), cmp_x);
    double d = min_dist(a, n);
    printf("%.2lf\n", d);

    return 0;
}

该程序首先读入点的数量和坐标，然后按照 x 坐标从小到大排序。然后调用 min_dist 函数求解最邻近点对的距离，并输出结果。该函数使用递归的方法，先将点集分成两半，然后分别在左右两半中递归求解最邻近点对的距离。接下来考虑跨越两个子集的点对，需要在 x 坐标在 [mid - min_dist, mid + min_dist] 范围内的点中，按照 y 坐标从小到大排序，然后依次判断相邻的点对之间的距离，更新最小距离即可。

数据事先预排序，设计算法O(nlogn)设计求解平面最邻近点对算法，c语言

以下是使用分治法和数据预排序求解平面最邻近点对问题的 C 语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAXN 10000

struct Point {
    double x, y;
};

int cmp_y(const void *a, const void *b) {
    struct Point *p1 = (struct Point *)a;
    struct Point *p2 = (struct Point *)b;
    return (p1->y < p2->y) ? -1 : 1;
}

double dist(struct Point p1, struct Point p2) {
    double dx = p1.x - p2.x;
    double dy = p1.y - p2.y;
    return sqrt(dx*dx + dy*dy);
}

double min_dist(struct Point *a, int n) {
    if (n <= 1) return 1e9;
    if (n == 2) return dist(a[0], a[1]);

    int mid = n / 2;
    double midx = a[mid].x;

    double d1 = min_dist(a, mid);
    double d2 = min_dist(a + mid, n - mid);
    double d = fmin(d1, d2);

    struct Point *b = (struct Point *)malloc(n * sizeof(struct Point));
    int m = 0;
    for (int i = 0; i < n; i++) {
        if (fabs(a[i].x - midx) < d) {
            b[m++] = a[i];
        }
    }

    qsort(b, m, sizeof(struct Point), cmp_y);
    for (int i = 0; i < m; i++) {
        for (int j = i + 1; j < m && b[j].y - b[i].y < d; j++) {
            double d3 = dist(b[i], b[j]);
            if (d3 < d) d = d3;
        }
    }

    free(b);
    return d;
}

int cmp_x(const void *a, const void *b) {
    struct Point *p1 = (struct Point *)a;
    struct Point *p2 = (struct Point *)b;
    return (p1->x < p2->x) ? -1 : 1;
}

int main() {
    int n;
    struct Point a[MAXN];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lf%lf", &a[i].x, &a[i].y);
    }

    qsort(a, n, sizeof(struct Point), cmp_x);
    double d = min_dist(a, n);
    printf("%.2lf\n", d);

    return 0;
}

该程序首先读入点的数量和坐标，然后按照 x 坐标从小到大排序。然后调用 min_dist 函数求解最邻近点对的距离，并输出结果。该函数使用递归的方法，先将点集分成两半，然后分别在左右两半中递归求解最邻近点对的距离。接下来考虑跨越两个子集的点对，需要在 x 坐标在 [mid - min_dist, mid + min_dist] 范围内的点中，按照 y 坐标从小到大排序，然后依次判断相邻的点对之间的距离，更新最小距离即可。与不使用数据预排序的算法不同，该程序在排序后的点集上进行求解，因此时间复杂度为 O(nlogn)。