P7883 平面最近点対（強化版）

NOIP 対策 1= ！！！#

問題#

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

解答#

$O (n^2)$ の列挙は確実に通らないので、分治法の最適化を考える

各区間内の良い計算は簡単だが、重要なのはどうやって統合するか？

$h$ を 2 つの子区間から返される最小値とする

$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;
}