平面最近点对

随机算法真的太酷了。

考虑这么一个流程：

首先将点的顺序随机打乱，然后考虑一个个加入点，同时维护已加入点的答案 $d$。

当将要新加入一个点的时候，先将已有点按 $d$ 分块，即点 $(x_i, y_i)$ 在 $\left(\left\lfloor\frac{x_i}d\right\rfloor, \left\lfloor\frac{y_i}d\right\rfloor\right)$ 块中。

考虑我们要新加入的点是 $(X, Y)$，先找到该点在哪一块，那么只需要搜索周围加上本块共九块内的点，即可找到可能与要加入的点更新答案的另一个点。又因为是以最近点对距离来分块，那么显然一块里最多有 $4$ 个点（分别在块的四个角上）。

如果加入的这个点成功更新了答案 $d$，那么就直接重构每个点的分块情况。

时间复杂度证明

首先，搜索点的时间复杂度是 $O(4 \times 9 \times n) = O(36n) = O(n)$。

考虑重构一次的概率，假设当前有 $i$ 个点，这 $i$ 个点中的最近点对是 $p_x, p_y$（我们不考虑有多对最近点对的情况，因为这是可以随机扰动以避免的）。那么相当于是等概率选择一个点令其最后加入，当该点为 $x$ 或 $y$ 时才会更新答案。则当前有 $i$ 个点时，重构的概率大概为 $\frac 2i = O(\frac 1i)$。

又因为第 $i$ 次重构时时间复杂度为 $O(i)$，那么重构部分的期望时间复杂度为 $O(\sum i \times \frac 1i) = O(n)$。

综上所述，上述算法期望时间复杂度为线性。

但是具体实现的话，需要用哈希表维护每块内的点，导致实际上跑不过 $O(n \log n)$（甚至 $O(n \log^2 n)$）。

模板题代码：

#include <unordered_map>
#include <algorithm>
#include <cstring>
#include <utility>
#include <cstdio>
#include <random>
#include <vector>
#include <queue>
#define mkp make_pair
#define fi first
#define se second
using namespace std;
typedef double db;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 400005;db ans;int sm;
const int dx[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
const int dy[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
int n, xx, yy;pii a[N];random_device Sd;mt19937 rnd(Sd());
inline ll hsh(int bx, int by){;return (bx + 1000000000) * 2000000001ll + by + 1000000000;}
inline db dist(pii a, pii b){return sqrt(1ll * (a.fi - b.fi) * (a.fi - b.fi) + 1ll * (a.se - b.se) * (a.se - b.se));}
template<typename T, const int M>
struct BHasher{inline int operator()(T x){return x % M;}};
template<typename T1, typename T2, int M, typename Hsr = BHasher<T1, M>>
struct HashMap{
	struct node{int nx;T1 ky;T2 vl;};
	int h[M];vector<node> nd;Hsr hsh;
	HashMap(){memset(h, -1, sizeof(h));}
	void clear(){memset(h, -1, sizeof(h)), nd.clear();}
	inline void insert(T1 k, T2 v){int p = hsh(k);
		nd.push_back((node){h[p], k, v});
		h[p] = nd.size() - 1;
	}
	template <typename F> inline void Enum(T1 k, F func){
		for (int i = h[hsh(k)];i != -1;i = nd[i].nx)
		if (nd[i].ky == k) func(nd[i].vl);
	}
};
HashMap<ll, int, 1000007> ps;
int main(){scanf("%d", &n);
	for (int i = 1;i <= n;i ++)
	scanf("%d%d", &a[i].fi, &a[i].se);
	shuffle(a + 1, a + n + 1, rnd), ans = 1e9;
	for (int i = 1;i <= n;i ++){bool flg = 0;
		int bx = floor(a[i].fi / ans), by = floor(a[i].se / ans);
		for (int o = 0;o < 9;o ++){
			int nx = bx + dx[o], ny = by + dy[o];
			ps.Enum(hsh(nx, ny), [&](int p){
				if (dist(a[i], a[p]) < ans)
				xx = i, yy = p, ans = dist(a[i], a[p]), flg = 1;
			});
		}
		if (flg){ps.clear();
			for (int j = 1;j <= i;j ++){
				bx = floor(a[j].fi / ans), by = floor(a[j].se / ans);
				ps.insert(hsh(bx, by), j);
			}
		}
		else ps.insert(hsh(bx, by), i);
	}printf("%lld", 1ll * (a[xx].fi - a[yy].fi) * (a[xx].fi - a[yy].fi) + 1ll * (a[xx].se - a[yy].se) * (a[xx].se - a[yy].se));
}