平面上最接近点对（分治法）

平面上的最接近点对

题目描述

给定平面上 $n$ 个点，找出其中的一对点的距离，使得在这 $n$ 个点的所有点对中，该距离为所有点对中最小的。

输入格式

第一行一个整数 $n$，表示点的个数。

接下来 $n$ 行，每行两个实数 $x,y$ ，表示一个点的行坐标和列坐标。

输出格式

仅一行，一个实数，表示最短距离，四舍五入保留 $4$ 位小数。

样例 #1

样例输入 #1

3
1 1
1 2
2 2
1
2
3
4

样例输出 #1

1.0000
1

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1\le n\le 10^4$，$0\le x,y\le 10^9$，小数点后的数字个数不超过 $6$。

题解：

对于给定的点序列，我们对它按x坐标的大小排序，接着取中点mid将点序列划分为两半，则求整个序列的最接近点对就分解成了三个子问题：

1. 求左侧序列的最近点对
2. 求右侧序列的最近点对
3. 求跨越左侧和右侧的最近点对

那么原问题的答案就是这三个中的最小值。

我们递归地对序列进行二分，求解到了前两个子问题的答案之后，得到二者中的较小值mmin，那么现在就需要解决第三个子问题了。

由于我们已经得到了一个较优的mmin值，考虑最极端的情况，对于我们需要找的跨越两侧的点对，一个是p[mid]本身，另一个是和p[mid]的y坐标相同的且横坐标之差恰好为mmin的点。

这已经是最极端的情况，横坐标之差如果再大一些，第三个子问题的解就不可能比mmin更优了。因此，我们可以将第三个子问题的答案的搜索范围压缩到与p[mid]横坐标之差小于mmin的点集。

仅仅在x坐标的维度进行压缩显然是有缺陷的，考虑一种非常极端的情况，我们上一步所求的与p[mid]横坐标之差小于mmin的点集所包含的点占总数的80%并且它们的y距离的差值高低起伏，也就是点几乎都分布在了过中点的垂线的附近但是y差值有大有小，那这个时候，显然，我们也要对y坐标进行约束，而约束的方法和x坐标是相通的。

所以，我们把上一步得到的点集按y坐标排序，然后对这个点集进行双重循环的枚举，更新mmin，由于序列按y有序，一旦出现y不满足约束（代码里已给出），则后面的点更不可能满足，直接break，枚举下一个点。

代码如下：

#include 
#include 
#include 
#include 
using namespace std;
const int inf = 999999997;
int n;

struct Point {
    int x, y;
}p[100001],temp[10001];

bool cmpx(Point a, Point b) { 
    return a.x < b.x || (a.x == b.x && a.y < b.y); 
}

bool cmpy(Point a, Point b) {
    return a.y < b.y || (a.y == b.y && a.x < b.x);
}

double dist(Point a, Point b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

double mindist(int low, int high) {
    if (low == high) {
        return inf;
    }
    if (low + 1 == high) {
        return dist(p[low], p[high]);
    }
    else {
        int mid = (low + high) / 2;
        double d1=mindist(low, mid);
        double d2 = mindist(mid + 1, high);
        double mmin = min(d1, d2);
        int len = 0;
        for (int i = low; i < high; i++) {
            if (fabs(p[i].x - p[mid].x) < mmin) {
                temp[++len] = p[i];
            }
        }
        sort(temp + 1, temp + 1 + len, cmpy);
        for (int i = 1; i < len; i++) {
            for (int j = i + 1; j <= len; j++) {
                if (temp[j].y - temp[i].y < mmin) {
                    mmin = min(mmin, dist(temp[i], temp[j]));
                }
                else {
                    break;
                }
            }
        }
        return mmin;
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i].x >> p[i].y;
    }
    sort(p + 1, p + 1 + n, cmpx);
    cout << fixed << setprecision(4) << mindist(1, n);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67