Closest points

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

long long rec_compute(vector<pair<int, int>> &points, int left, int right) {
    if (right-left <= 1) return LLONG_MAX;
    if (right-left == 2) {
        long long dx = points[left].first-points[right-1].first;
        long long dy = points[left].second-points[right-1].second;
        return dx*dx + dy*dy;
    }

    int mid = (left+right) / 2;
    long long minL = rec_compute(points, left, mid);
    long long minR = rec_compute(points, mid, right);
    long long d = min(minL, minR);

    vector<pair<int, int>> close;
    for (int i = left; i < right; i++) {
        if (abs(points[i].first-points[mid].first) < d) {
            close.push_back(points[i]);
        }
    }

    sort(close.begin(), close.end(), [](const pair<int, int> &a, const pair<int, int> &b){
        return a.second < b.second;
    });

    long long d_close = d;
    for (size_t i = 0; i < close.size(); i++) {
        for (size_t j = i+1; j < close.size() && j < i+8; j++) {
            if (close[j].second-close[i].second < d_close) {
                long long dx = close[i].first-close[j].first;
                long long dy = close[i].second-close[j].second;
                d_close = min(d_close, dx*dx + dy*dy);
            } else {
                break;
            }
        }
    }

    return min(d, d_close);
}

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

    sort(points.begin(), points.end());

    cout << rec_compute(points, 0, 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