peltorator

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