黄阿信的个人博客

问题描述

对于给定的n个点，求出这些点的最小的距离。

解法一：暴力法

遍历任意两点之间的距离，找出最小值。

/*
 * @Description:
 * @Author: Yale_Xin
 * @Date: 2020-04-02 20:37:23
 * @LastEditTime: 2020-04-02 21:23:54
 * @LastEditors: Yale_Xin
 */
#include <math.h>
#include <stdio.h>
double distance(double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
typedef struct point {
    double x, y;
} mPoint;
mPoint p[120], mid[120];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lf %lf", &p[i].x, &p[i].y);
    }
    double min = 9999.0;
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++) {
            double t = distance(p[i].x, p[i].y, p[j].x, p[j].y);
            min = min < t ? min : t;
        }
    printf("%lf", min);
    return 0;
}

算法复杂度是：O（n²）

解法二：分治法

先将点集按照x坐标的大小进行排序
递归进行3，4，5步骤
取一条中线，将点集分成左右两部分，尽量把点集分为数量相同的两半，找出左边最小的点距离DL和右边最小的点距离DR，取二者的较小者minD=min(DL,DR)
合并：以中线为中心，半径为minD做圆，将左右两边的点中处于该圆的点保存在一个数组中，求出这些点中的最小距离，关于这个距离，可以先按照y坐标的大小进行排序，接着，对于每一个点P0(x1,y1)，只要计算出紧接在P0后面的6个点和P0之间的距离，取较小值，该值就是P0和距离DR中的点的最小值（假设P0在DL），计算该数组中的每一个点的最小值，并找出在这里边的最小值m。
取m和minD的较小者，即为所求。

/*
 * @Description:
 * @Author: Yale_Xin
 * @Date: 2020-04-02 15:59:50
 * @LastEditTime: 2020-04-02 21:03:04
 * @LastEditors: Yale_Xin
 */
#include <math.h>
#include <stdio.h>
// 交换两个数的宏定义
#define swap(a, b)    \
    {                 \
        mPoint t = a; \
        a = b;        \
        b = t;        \
    }
// 计算两个点之间的距离函数
double distance(double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
typedef struct point {
    double x, y;
} mPoint;
mPoint p[100], mid[100];
int n;
void q_sort(int l, int r) {
    if (l >= r)
        return;
    int i = l, j = i + 1;
    mPoint key = p[l];
    for (; j <= r; j++) {
        if (p[j].x <= key.x) {
            i++;
            swap(p[i], p[j]);
        }
    }
    swap(p[l], p[i]);
    q_sort(l, i - 1);
    q_sort(i + 1, r);
}
void q_sort_y(int l, int r) {
    if (l >= r)
        return;
    int i = l, j = i + 1;
    mPoint key = mid[l];
    for (; j <= r; j++) {
        if (mid[j].y <= key.y) {
            i++;
            swap(mid[i], mid[j]);
        }
    }
    swap(mid[l], mid[i]);
    q_sort(l, i - 1);
    q_sort(i + 1, r);
}
double find_minD(int l, int r) {
    if (r - l == 2) {
        double d1, d2, d3;
        d1 = distance(p[l].x, p[l].y, p[r + 1].x, p[r + 1].y);
        d2 = distance(p[l].x, p[l].y, p[r].x, p[r].y);
        d3 = distance(p[l + 1].x, p[l + 1].y, p[r].x, p[r].y);
        d1 = d1 < d2 ? d1 : d2;
        d1 = d1 < d3 ? d1 : d3;
        return d1;
    } else if (l + 1 == r) {
        return distance(p[l].x, p[l].y, p[r].x, p[r].y);
    } else {
        // 分别是距离中线距离小于min的点的数量、中线位置
        int number = 0, mid_x = p[(l+r)/2].x;
        double Lmin, Rmin, min, mid_min = 32767;
        Lmin = find_minD(l, (l+r) / 2);
        Rmin = find_minD((l+r) / 2 + 1, r);
        min = Lmin < Rmin ? Lmin : Rmin;
        // 以中线为为中心，寻找左右两边中距离中线距离小于等于min的点
        for (int i = l; i <= r; i++) {
            if ((p[i].x - mid_x) < min) {
                mid[number++] = p[i];
            }
        }
        // 将得到的数组根据坐标y的值进行排序 求出该数组中最小点对值
        if (number > 0) {
            q_sort_y(0, number - 1);
            for (int i = 0; i < number - 1; i++) {
                int count = 0;
                for (int j = i + 1; j < number; j++) {
                    double t = distance(p[i].x, p[i].y, p[j].x, p[j].y);
                    mid_min = mid_min < t ? mid_min : t;
                    if (++count > 7) {
                        break;
                    }
                }
            }
        }
        return min < mid_min ? min : mid_min;
    }
}
int main() {
    double min_d;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lf %lf", &p[i].x, &p[i].y);
    }
    //先按照x坐标进行排序
    q_sort(1, n);
    
    min_d = find_minD(1, n);
    printf("%lf",min_d);
    return 0;
}

算法复杂度是：O（nlogn）