问题

给出平面上一系列点 $P=\{(x,y)|x,y\in R\}$ ，求任意两点之间欧几里得距离的最小值 $\min(\sqrt{(p.x-q.x)^2+(p.y-q.y)^2})\quad p,q\in P\;and\;p\ne q$

解析

$dis_{pq}=\sqrt{(p.x-q.x)^2+(p.y-q.y)^2}$ 记作 $pq$ 两点之间的欧几里得距离

暴力做法

很容易想到对这个问题暴力求解的方法，对于每一个点 $p$ ,计算它与其余所有点之间的距离，取最小值即可 $ans=\min(dis_{pq})，p\ne q$
时间复杂度为 $O(n^2)$

分治策略

首先按照分治策略的基本套路，一般都是将问题分解为若干个子问题，然后将子问题的结果合并为大问题的结果

首先考虑分治的终点
- 显然当所求的点只有两个的时候，最近距离就是两点间距离
- 当所求的点有一个的时候，可以取最近距离为无穷大(一个答案肯定无法取到的极大值)
考虑如何合并子问题
- 对于整体的答案，可以分为两类，一类为子问题的最近距离(所有点都取子问题内的)，一类为子问题之间的最近距离(两点分别取在不同的子问题内)
- 对于第一类情况，在分治是已经求得结果
- 对于第二类情况，我们假设第一类情况求得的最优结果为 $d$ ，考虑将问题划分为两个子问题
  显然两个子问题之间的最优结果一定在两个子问题交界处合并，因为已经有了最优结果 $d$ ，那么更优的结果一定不小于 $d$ ,这个限制条件非常重要

具体步骤
1.首先对所有的点按照 $x$ 轴升序排列，以所有点 $x$ 轴坐标的中位数为界，将问题划分为左右两个子问题，分别解决
2.若问题规模小于等于 $2$ ，则直接计算，否则继续分治
3.对于分治得到的两个结果，可以得到一个当前的最优解 $d$ ,要合并两个问题的结果，也就是分别在左右两个子问题内取一个点，计算最小距离，显然对于距离中位线距离超过 $d$ 的点可以直接忽略，这些点光是 $x$ 轴的距离就已经大于 $d$ 了
4.我们对所有符合步骤3中所描述条件的点放进一个集合中，集合记作 $T$ ，对 $T$ 中的点按照 $y$ 轴坐标升序排列，对每一个点向后枚举，直到点的 $y$ 轴坐标差值大于 $d$ ，退出当前循环，对所有枚举的答案取最小值
看似暴力的枚举，其实复杂度是线性的，也就是O(n)
图片说明
我们假设以其中一个点为中心，做一个边长为 $2d$ 的正方形，图中红点即为中心，最外侧黑色线框为所构造的三角形
我们以中心右侧为例，将横向边对半分，每一半长度为 $\frac d2$ ,纵向边 $3$ 等分，每一部分为 $\frac{2d}{3}$

因为在上一步分治过程中求得左右子问题的答案最小值为 $d$ ,则右侧任意两点之间的距离不小于 $d$
在一个矩形中，对角线是其中最长的直线，如图中橙色线标识，可由勾股定理得到每个小矩形的对角线长度为 $\frac{5d}{6}\lt d$ 所以在一个点附近如途中小矩形的范围内，不会有第二个点
根据大线框与小线框的关系，显然大线框内不超过 $6\times 2 =12$ 个点，所以枚举的点的数量不超过12个
枚举的总个数不超过 $12n$
所以枚举的复杂度是线性的，也就是 $O(n)$
设计

// #pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <list>
#include <cstdlib>
#include <bitset>
#include <assert.h>
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
// char buf[(1 << 21) + 1], * p1 = buf, * p2 = buf;
// #define int long long
#define lowbit(x) (x & (-x))
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
#define pb push_back
typedef unsigned long long ull;
typedef long long ll;
typedef std::pair<ll, ll> pii;
#define bug puts("BUG")
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;
template <class T>
inline void read(T &x)
{
    int sign = 1;char c = getchar();x = 0;
    while (c > '9' || c < '0'){if (c == '-')sign = -1;c = getchar();}
    while (c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();}
    x *= sign;
}
#ifdef LOCAL
    FILE* _INPUT=freopen("..\\input.txt", "r", stdin);
    // FILE* _OUTPUT=freopen("output.txt", "w", stdout);
#endif
using namespace std;
const int maxn = 1e5 + 10;
struct point
{
    double x, y;
} p[maxn];

double dis(point a,point b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
bool cmpx(point a,point b)
{
    return a.x < b.x;
}
bool cmpy(point a,point b)
{
    return a.y < b.y;
}
double cal(point a[],int len)
{
    if(len==1)
        return inf;
    if(len==2)
        return dis(a[0], a[1]);
    double p = a[len / 2 - 1].x;
    int mid = len / 2;
    double d = min(cal(a, mid), cal(a + mid, len - mid));
    int tot = 0;
    for (int i = 0; i < len; ++i)
        if (fabs(p - a[i].x) <= d)
            swap(a[tot++], a[i]);
    sort(a, a + tot, cmpy);
    for (int i = 0; i < tot; ++i)
    {
        for (int j = i + 1; j < tot; ++j)
        {
            if (a[j].y - a[i].y > d)
                break;
            d = min(d, dis(a[i], a[j]));
        }
    }
    return d;
}

int main()
{
    int n;
    read(n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%lf%lf", &p[i].x, &p[i].y);
    }
    sort(p, p + n, cmpx);
    printf("%.6f\n", cal(p, n));
}

分析

在前面的解析中已经证明枚举的复杂度是线性的，也就是合并子问题的复杂度是线性的
可以得出如下递推式,假设点的个数为 $2^k,k\in Z^*$ ,其中 $g,h$ 分别为排序的复杂度和合并的复杂度 $\left.\begin{cases} f(2^k)=2f(2^{k-1})+g(2^k)+h(2^k)\\ f(2)=f(1)=1 \end{cases}\right.$
通过累加法可以消去部分项

$\left.\begin{align*} f(2^k)&=2^1f(2^{k-1})+g(2^k)+h(2^k)\\ 2^1f(x^{k-1})&=2^2f(2^{k-2})+2^1g(2^{k-1})+2^1h(2^{k-1})\\ &\dots\\ 2^{k-1}f(2)&=2^{k-1}\times 1 \end{align*}\right.$
将所有式子相加，消去等号左边相同的项

$f(2^k)=\sum_{i=0}^{k-1}{2^ig(2^{k-i})}+2^ih(2^{k-i})$

考虑用效率较高的归并排序，或堆排序等算法，则排序的复杂度是 $O(n\log(n))$
最终总复杂度为

$\begin{align*} f(2^k)&=\sum_{i=0}^{k-1}{(k-i)2^k+2^k}\\ &=\sum_{i=0}^{k-1}{(k-i+1)2^k}\\ &=2^k\sum_{i=1}^k{i}\\ &=2^k\frac{(k+1)k}{2} \sim O(2^kk^2)\\ \end{align*}$
将 $2^k=x$ 带入
最终复杂度为 $o(n\log^2(n))$
也可以用时间环空间，先排序按 $x$ 和 $y$ 分别排序，然后按中位线线性的划分给左右子问题，复杂度可降为 $O(n\log(n))$

源码

传送门

算法课-平面最近点对

问题

解析

暴力做法

分治策略

设计

分析

源码