Closest Pair Of Points Linear Algorithm

#include <bits/stdc++.h>

using namespace std;

struct Point {
    long long x, y;

    Point(long long x, long long y) : x(x), y(y) {}
};

long long distance_square(Point a, Point b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

double find_closest_points_distance(vector<Point> points) {
    assert(points.size() > 1);
    mt19937 rnd(1234);
    shuffle(points.begin(), points.end(), rnd);
    long long ans_square = distance_square(points[0], points[1]);
    long long ans = sqrt(ans_square);
    if (ans_square == 0) {
        return 0;
    }
    unordered_map<long long, vector<Point>> grid;

    auto correct_division = [&](long long a, long long b) -> long long { // avoiding troubles with negative numbers
        long long reminder = a % b;
        if (reminder < 0) {
            reminder += b;
        }
        return (a - reminder) / b;
    };
    auto get_point_hash = [&](Point p) -> long long {
        return correct_division(p.x, ans) * 10000007 + correct_division(p.y, ans);
    };
    grid[get_point_hash(points[0])].push_back(points[0]);
    grid[get_point_hash(points[1])].push_back(points[1]);

    for (size_t i = 2; i < points.size(); i++) {
        long long new_ans_square = ans_square;

        for (int dx = -1; dx <= 1; dx++) {
            for (int dy = -1; dy <= 1; dy++) {
                for (Point q : grid[get_point_hash(Point(points[i].x + dx * ans, points[i].y + dy * ans))]) {
                    new_ans_square = min(new_ans_square, distance_square(points[i], q));
                }
            }
        }

        if (new_ans_square < ans_square) {
            ans_square = new_ans_square;
            ans = sqrt(new_ans_square);
            if (ans_square == 0) {
                return 0;
            }
            grid.clear();
            for (size_t j = 0; j < i; j++) {
                grid[get_point_hash(points[j])].push_back(points[j]);
            }
        }
        grid[get_point_hash(points[i])].push_back(points[i]);
    }
    return sqrt(ans_square);
}

int main() {
    int n;
    cin >> n;
    vector<Point> points;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        points.emplace_back(x, y);
    }
    cout << find_closest_points_distance(points) << endl;
}