peltorator

Closest Pair Of Points Linear Algorithm

May 20th, 2021 (edited)
1,051
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.30 KB | None | 0 0
  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. }
Add Comment
Please, Sign In to add comment