问题简述

$给定二维平面上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;
}