# Closest Pair Of Points Linear Algorithm

May 20th, 2021 (edited)
1,537
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2.
3. using namespace std;
4.
5. struct Point {
6.     long long x, y;
7.
8.     Point(long long x, long long y) : x(x), y(y) {}
9. };
10.
11. long long distance_square(Point a, Point b) {
12.     return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
13. }
14.
15. double find_closest_points_distance(vector<Point> points) {
16.     assert(points.size() > 1);
17.     mt19937 rnd(1234);
18.     shuffle(points.begin(), points.end(), rnd);
19.     long long ans_square = distance_square(points[0], points[1]);
20.     long long ans = sqrt(ans_square);
21.     if (ans_square == 0) {
22.         return 0;
23.     }
24.     unordered_map<long long, vector<Point>> grid;
25.
26.     auto correct_division = [&](long long a, long long b) -> long long { // avoiding troubles with negative numbers
27.         long long reminder = a % b;
28.         if (reminder < 0) {
29.             reminder += b;
30.         }
31.         return (a - reminder) / b;
32.     };
33.     auto get_point_hash = [&](Point p) -> long long {
34.         return correct_division(p.x, ans) * 10000007 + correct_division(p.y, ans);
35.     };
36.     grid[get_point_hash(points[0])].push_back(points[0]);
37.     grid[get_point_hash(points[1])].push_back(points[1]);
38.
39.     for (size_t i = 2; i < points.size(); i++) {
40.         long long new_ans_square = ans_square;
41.
42.         for (int dx = -1; dx <= 1; dx++) {
43.             for (int dy = -1; dy <= 1; dy++) {
44.                 for (Point q : grid[get_point_hash(Point(points[i].x + dx * ans, points[i].y + dy * ans))]) {
45.                     new_ans_square = min(new_ans_square, distance_square(points[i], q));
46.                 }
47.             }
48.         }
49.
50.         if (new_ans_square < ans_square) {
51.             ans_square = new_ans_square;
52.             ans = sqrt(new_ans_square);
53.             if (ans_square == 0) {
54.                 return 0;
55.             }
56.             grid.clear();
57.             for (size_t j = 0; j < i; j++) {
58.                 grid[get_point_hash(points[j])].push_back(points[j]);
59.             }
60.         }
61.         grid[get_point_hash(points[i])].push_back(points[i]);
62.     }
63.     return sqrt(ans_square);
64. }
65.
66. int main() {
67.     int n;
68.     cin >> n;
69.     vector<Point> points;
70.     for (int i = 0; i < n; i++) {
71.         int x, y;
72.         cin >> x >> y;
73.         points.emplace_back(x, y);
74.     }
75.     cout << find_closest_points_distance(points) << endl;
76. }