22pts TLE 正常分治思路

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 400010;
int n, b[N];
struct node { int x, y; } a[N];
bool cmp(node a, node b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
bool cmp1(int x, int y) { return a[x].y < a[y].y; }
inline ll dis(int i, int j) { return 1ll * (a[i].x - a[j].x) * (a[i].x - a[j].x) + 1ll * (a[i].y - a[j].y) * (a[i].y - a[j].y); }
ll solve(int l, int r) {
	ll d = 0x7f7f7f7f;
	if (l == r) return d;
	if (l + 1 == r) return dis(l, r);
	int mid = l + r >> 1;
	ll d1 = solve(l, mid), d2 = solve(mid + 1, r);
	d = min(d1, d2);
	int k = 0;
	for (int i = l; i <= r; i++)
		if (abs(a[mid].x - a[i].x) < d) b[++k] = i;
	sort(b + 1, b + k + 1, cmp1);
	for (int i = 1; i < k; i++)
		for (int j = i + 1; j <= k && a[b[j]].y - a[b[i]].y < d; j++) d = min(d, dis(b[i], b[j]));
	return d;
}
int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y;
	sort(a + 1, a + n + 1, cmp);
	cout << solve(1, n) << '\n';
	return 0;
}