平面最近点对问题

问题简述

$给定二维平面上N个点,定义距离为欧氏距离$
$对于N个点组成的所有点对(i, j),i\ne j, i, j\in[1,N]$
$求最小的(i,j)点对距离$

暴力求解

  • 显然暴力求解的时间复杂度是$O(n^2)$的,是否可以优化呢?存在带$log$的算法么?
    考虑一下分治法

分治法

由主定理我们可以知道:$T(n)=2T(n/2)+O(n)\Rightarrow O(nlogn)$
这就需要我们尽可能的将原问题划分成2个相等的子问题
并且划分2个子问题,合并2个子问题,或者处理1个子问题对另1个子问题的影响不能超过$O(n)$

  • 划分
    如果将所有的点按照二维偏序(即横坐标$x$为第一关键字,纵坐标$y$为第二关键字)排序
    那么通过中间的那个点就可以将所有点划分成均等的2部分了
    这样我们以$O(nlogn)-O(1)$的时间复杂度做到了这一点

  • 递归处理子问题

    假设均等的2部分的子问题的答案分别是$d_1,d_2$,显然当前答案就是$d=min(d_1,d_2)$
    $(1)$类型的答案为$d$,但是我们发现$(2)$类型的答案很有可能$\le d$
    即中间那个点,在它两边的点形成的点对很有可能也会是答案
    也就说1个子问题对另1个子问题产生了影响,接下来思考如何计算这一部分的答案

  • 子问题间的影响

    • 可能产生影响的点
      对于中间点p来说,显然左右横坐标距离d以内的才是要考虑的点
      即若p点坐标为$(x,y)$,那么要考虑的点的横坐标$x-d<x’<x+d$,其它的点显然不能产生影响
      找到了这些可能产生影响的点后,点最坏有$n$个,如果一一枚举还是$O(n^2)$
      难道就逃脱不了$n^2$的命运了么?

    • 能对一个点贡献答案的点
      对于其中一个点$p_1$,能产生答案的点只考虑$y$比它大的那部分(这样一对点不会重复枚举)
      即若$p_1$点坐标为$(x,y)$,那么要考虑的点的横坐标$x-d<x’<x+d$,纵坐标$y \le y’ \le y +d$
      也就是说对$p_1$贡献答案的点应该就是如图那样的矩形部分

    • 矩形内至多有6个点
      我说矩形里至多有6个点你信不信!我们来证明一下:

      将矩形$R$的长为$2d$的边三等分,宽为$d$的边二等分
      这样我们得到了6个$\frac{2d}{3}\times \frac{d}{2}$的小矩形
      假设位于中轴线两侧的4个小矩形中有多于2个点,
      设$u,v$是位于同一小矩形中的两个点,则
      $d(u,v)=\sqrt{(x_u - x_v) ^ 2 + (y_u-y_v) ^ 2 }\le \sqrt{(d / 2) ^ 2 + (2d / 3) ^ 2} = \sqrt{25 / 36 * d ^ 2}=\frac{5d}{6} < d$
      因为递归已经算出两边子问题解为最优为$d$了,这显然是矛盾的,所以每个小矩形最多只能有1个点
      但是跨越中轴线的2个小矩形中可能会有多于2个点,但我们发现它们只能在中轴线上
      不然就与其他4个小矩形中的点构成了小于$d$的点对了,但是由于合法性最坏的点对如下图:

      这样最多就只有6个点了,重合点是非法的,因为会被分到2边,然后违法了$d$是最优解的条件
      $\blacksquare$

    • 时间复杂度分析
      有一个对$y$坐标排序,我们可以通过归并来实现,这样就还是$O(n)$
      总时间复杂度:$T(n)=2T(n/2)+O(6n)\Rightarrow O(nlogn)$

分治法实现

$UVA 10245 模版裸题:$

//
//  Created by TaoSama on 2016-03-18
//  Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e4 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n;
typedef pair<double, double> P;
P a[N];

double dfs(int l, int r) {
    if(l == r) return INF;
    int m = l + r >> 1;
    double x = a[m].first;

    double d = min(dfs(l, m), dfs(m + 1, r));
    inplace_merge(a + l, a + m + 1, a + r + 1, [](P x, P y) {
        return x.second < y.second;  //按照y来归并2个数组
    });

    vector<int> v;
    for(int i = l; i <= r; ++i) {
        if(abs(a[i].first - x) >= d) continue; //距离中轴小于d点加入

        for(int j = 0; j < v.size(); ++j) {
            int k = v[v.size() - 1 - j];  //倒着检查y坐标相差小于d的点
            double dy = a[i].second - a[k].second;
            if(dy >= d) break;
            double dx = a[i].first - a[k].first;
            d = min(d, hypot(dx, dy));
        }
        v.push_back(i);
    }
    return d;
}

int main() {
#ifdef LOCAL
    freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
//  freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    while(scanf("%d", &n) == 1 && n) {
        for(int i = 1; i <= n; ++i) scanf("%lf%lf", &a[i].first, &a[i].second);
        sort(a + 1, a + 1 + n);

        double d = dfs(1, n);
        if(d >= 1e4) {puts("INFINITY"); continue;}
        printf("%.4f\n", d);
    }
    return 0;
}