Closest Pair of Points
O(n log n)Smallest distance between any two of n points, returned SQUARED so everything stays in integers. Both versions lean on the same packing fact: once a best distance d is known, only O(1) already-seen points can sit within d of the current one. The C++ code sweeps left to right keeping a strip of recent points in a set ordered by y; the Python code is the classic divide and conquer with a y-sorted merge (no sorted-set in the stdlib).
// use it on
CSES: Minimum Euclidean Distance ↗
Asks for the squared distance, which is exactly what the template returns, with no floating point anywhere. 2·10^5 points, so the O(n²) all-pairs scan is out.
// the code
typedef long long ll;
// squared distance of the closest pair (sweep, strip ordered by y)
ll closest_pair(vector<pair<ll, ll>> pts) { // points as (x, y), n >= 2
sort(pts.begin(), pts.end());
set<pair<ll, ll>> strip; // (y, x) of points within d behind the sweep
ll best = LLONG_MAX;
size_t left = 0;
for (auto& [x, y] : pts) {
ll d = (ll)sqrtl((long double)best) + 1;
while (left < pts.size() && pts[left].first < x - d) {
strip.erase({pts[left].second, pts[left].first});
left++;
}
for (auto it = strip.lower_bound({y - d, LLONG_MIN});
it != strip.end() && it->first <= y + d; ++it) {
ll dx = it->second - x, dy = it->first - y;
best = min(best, dx * dx + dy * dy);
}
strip.insert({y, x});
}
return best;
}// more geometry