Closest points

#include <bits/stdc++.h>
using namespace std;

using Point = pair<int,int>;

long long dist(const Point &p1, const Point &p2) {
    long long dx = (long long)p1.first - p2.first;
    long long dy = (long long)p1.second - p2.second;
    return dx*dx + dy*dy;
}

long long bruteForce(const vector<Point> &P, int n) {
    long long min_dist = LLONG_MAX;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            min_dist = min(min_dist, dist(P[i], P[j]));
        }
    }
    return min_dist;
}

long long stripClosest(const vector<Point> &strip, int size, long long d) {
    long long min_dist = d;
    for (int i = 0; i < size; i++) {
        for (int j = i+1; j < size && (long long)(strip[j].second - strip[i].second)*(strip[j].second - strip[i].second) < min_dist; j++) {
            min_dist = min(min_dist, dist(strip[i], strip[j]));
        }
    }
    return min_dist;
}

long long closestUtil(const vector<Point> &Px, const vector<Point> &Py, int n) {
    if (n <= 6) {
        return bruteForce(Px, n);
    }

    int mid = n / 2;
    Point midPoint = Px[mid];

    vector<Point> Pyl, Pyr;
    Pyl.reserve(mid);
    Pyr.reserve(n - mid);
    for (const auto &point : Py) {
        if (point.first < midPoint.first || (point.first == midPoint.first && point.second < midPoint.second)) {
            Pyl.push_back(point);
        } else {
            Pyr.push_back(point);
        }
    }

    long long dl = closestUtil(vector<Point>(Px.begin(), Px.begin() + mid), Pyl, mid);
    long long dr = closestUtil(vector<Point>(Px.begin() + mid, Px.end()), Pyr, n - mid);

    long long d = min(dl, dr);

    vector<Point> strip;
    for (const auto &p : Py) {
        long long dx = (long long)p.first - midPoint.first;
        if (dx*dx < d) {
            strip.push_back(p);
        }
    }

    return min(d, stripClosest(strip, (int)strip.size(), d));
}

long long closest(vector<Point> &P, int n) {
    vector<Point> Px = P;
    vector<Point> Py = P;
    sort(Px.begin(), Px.end(), [](const Point &a, const Point &b) { return a.first < b.first; });
    sort(Py.begin(), Py.end(), [](const Point &a, const Point &b) { return a.second < b.second; });
    return closestUtil(Px, Py, n);
}

int main() {
    int n; cin >> n;
    vector<Point> points(n);
    for (int i = 0; i < n; i++) {
        cin >> points[i].first >> points[i].second;
    }

    cout << closest(points, n) << "\n";
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED