P7883 平面最近点对（加强加强版）

备战NOIP 1= ！！！

题目

P7883 平面最近点对（加强加强版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题解

$O(n^2)$ 枚举肯定过不了，考虑分治优化

每个区间内的好算，关键是如何合并？

记$h$表示两子区间返回的最小值

在$mid$点的附近$h$距离内找点，可能更新答案

按纵坐标枚举即可

锅

如果 TLE - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

代码

#include<bits/stdc++.h>
#define PII pair<long long, long long> 
using namespace std;
#define x first
#define y second 
const int N = 4e5 + 10;
PII p[N];
int n;
#define ll long long 
long long merge(int l, int r)
{
//	cout << l << " " << r << "----------\n";
	if(l == r) return 0x3f3f3f3f3f3f3f3f; 
	int mid = (l + r) >> 1;
	ll h1 = merge(l, mid);
	ll h2 = merge(mid + 1, r);
	ll h = min(h1, h2);
	vector <PII> B;
	for(int i = l;i <= r;i++)
	{
		if((p[i].x - p[mid].x) * (p[i].x - p[mid].x) < h) B.push_back({p[i].y, p[i].x}); 
	}
	sort(B.begin(), B.end());
//	for(auto i : B)
//	{
//		cout << i.x << " " << i.y << endl;
//	}
	for(int i = 0;i < B.size();i++)
	{
		for(int q = i + 1;q < B.size();q++)
		{
			if((B[i].first - B[q].first) * (B[i].first - B[q].first) > h) break;
			h = min(h, (B[i].first - B[q].first) * (B[i].first - B[q].first) + (B[i].second - B[q].second) * (B[i].second - B[q].second));
		}
	}
//	cout << l << " " << r << "  " << h << endl;
	return h;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++)
		cin >> p[i].x >> p[i].y;

	sort(p + 1, p + 1 + n);

	cout << merge(1, n) << endl;
	return 0;
}