---
tags: codebook
---

{%hackmd theme-dark %}

# closest pair

## STL

ll distance(const auto& a, const auto& b) {
	return (a.first - b.first) * (a.first - b.first)
	       + (a.second - b.second) * (a.second - b.second);
}
struct cmp {
	bool operator()(const pair<ll, ll>& a, const pair<ll, ll>& b) const {
		return a.second < b.second
		       || (a.second == b.second && a.first < b.first);
	}
};
long long closest_pair(vector<pair<ll, ll>>& v) {
	set<pair<ll, ll>, cmp> s;
	long long d = numeric_limits<long long>::max();
	for (size_t r = 0, l = 0; r != v.size(); r++) {
		while (l <= r && v[r].first - v[l].first > sqrt(d))
			s.erase(v[l++]);
		auto i = s.insert(v[r]).first, j = i;
		for (int k = 0; ++j != s.end() && k != 2; k++)
			d = min(d, distance(*i, *j));
		j = i;
		for (int k = 0; j-- != s.begin() && k != 2; k++)
			d = min(d, distance(*i, *j));
	}
	return d;
}
inline void solve() {
	int n; cin >> n;
	V<P<ll>> v(n);
	for (auto& [a, b] : v)
		cin >> a >> b;
	sort(v.begin(), v.end());
	cout << closest_pair(v) << endl;
}

## Recursive

inline ll d(P<ll> a, P<ll> b) {
	return (a.first - b.first) * (a.first - b.first)
	       + (a.second - b.second) * (a.second - b.second);
}
inline ll dx(P<ll> a, P<ll> b) {
	return (a.first - b.first) * (a.first - b.first);
}
ll closest_pair(const V<P<ll>>& v, int l, int r) {
	if (r - l < 2) return inf;
	int m = (l + r) >> 1;
	ll ret = min(closest_pair(v, l, m), closest_pair(v, m, r));
	V<P<ll>> tmp;
	for (int i = m; i < r && dx(v[i], v[m]) < ret; i++)
		tmp.emplace_back(v[i]);
	for (int i = m - 1; i >= l && dx(v[i], v[m]) < ret; i--)
		tmp.emplace_back(v[i]);
	sort(tmp.begin(), tmp.end(), [](auto a, auto b) {
		return a.second < b.second;
	});
	// debug(tmp);
	for (int i = 0; i < (int)tmp.size(); i++)
		for (int j = i + 1; j < min((int)tmp.size(), i + 4); j++)
			ret = min(ret, d(tmp[i], tmp[j]));
	// debug(l, r, ret);
	return ret;
}
inline void solve() {
	int n; cin >> n;
	V<P<ll>> v(n);
	for (auto& [a, b] : v)
		cin >> a >> b;
	sort(v.begin(), v.end());
	cout << closest_pair(v, 0, n) << endl;
}