Luogu P1429 平面最近点对（加强版）

题目链接：传送门

这哪里叫什么加强版…可能只是$n^2$n2过不去了而已
随便分治一下
选择$mid$mid的一边挑出横坐标差小于递归分治小区间答案的点
因为横坐标如果再大于答案它也不可能成为答案
然后再与另一边同样的方法找点
更新$ans$ans

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define A 200010
#define B 2010

using namespace std;
typedef long long ll;
struct node {
	double x, y;
	friend bool operator < (const node a, const node b) {
		return a.x == b.x ? a.y < b.y : a.x < b.x;
	}
}e[A], t[A];
bool cmp(node a, node b) {
	return a.x > b.x;
}
int n; double ans = INT_MAX;
double dist(double x, double y, double xx, double yy) {
	return sqrt((x - xx) * (x - xx) + (y - yy) * (y - yy));
}
void dac(int l, int r) {
	if (l == r) return;
	int m = (l + r) >> 1, cnt = 0;
	dac(l, m); dac(m + 1, r);
	for (int i = m + 1; i <= r; i++)
		if (e[i].x - e[m].x < ans) t[++cnt] = e[i];
	sort(e + l + 1, e + m + 1, cmp); //这个sort不加会快一些...不加sort的话下面的break改成continue
	for (int i = l; i <= m; i++) {
		if (e[m].x - e[i].x >= ans) break;
		for (int j = 1; j <= cnt; j++) ans = min(ans, dist(e[i].x, e[i].y, t[j].x, t[j].y));
	}
}

int main(int argc, char const *argv[]) {
	cin >> n;
	for (int i = 1; i <= n; i++) scanf("%lf%lf", &e[i].x, &e[i].y);
	sort(e + 1, e + n + 1); dac(1, n);
	cout << fixed << setprecision(4) << ans << endl;
}