# Closest Pair Of Points Linear Algorithm

May 20th, 2021
756
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 distanceSquare(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 findClosestPointsDistance(vector<Point> points) {
16.     assert(points.size() > 1);
17.     mt19937 rnd(1234);
18.     shuffle(points.begin(), points.end(), rnd);
19.     long long anssq = distanceSquare(points[0], points[1]);
20.     long long ans = sqrt(anssq);
21.     if (anssq == 0) {
22.         return 0;
23.     }
24.     unordered_map<long long, vector<Point>> grid;
25.
26.     auto trueDivision = [&](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 getPointHash = [&](Point p) -> long long {
34.         return trueDivision(p.x, ans) * 10000007 + trueDivision(p.y, ans);
35.     };
36.     grid[getPointHash(points[0])].push_back(points[0]);
37.     grid[getPointHash(points[1])].push_back(points[1]);
38.
39.     for (size_t i = 2; i < points.size(); i++) {
40.         long long newanssq = anssq;
41.
42.         for (int dx = -1; dx <= 1; dx++) {
43.             for (int dy = -1; dy <= 1; dy++) {
44.                 for (Point q : grid[getPointHash(Point(points[i].x + dx * ans, points[i].y + dy * ans))]) {
45.                     newanssq = min(newanssq, distanceSquare(points[i], q));
46.                 }
47.             }
48.         }
49.
50.         if (newanssq < anssq) {
51.             anssq = newanssq;
52.             ans = sqrt(newanssq);
53.             if (anssq == 0) {
54.                 return 0;
55.             }
56.             grid.clear();
57.             for (size_t j = 0; j < i; j++) {
58.                 grid[getPointHash(points[j])].push_back(points[j]);
59.             }
60.         }
61.         grid[getPointHash(points[i])].push_back(points[i]);
62.     }
63.     return sqrt(anssq);
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.push_back(Point(x, y));
74.     }
75.     cout << findClosestPointsDistance(points) << endl;
76. }
RAW Paste Data