Advertisement
Guest User

Untitled

a guest
Dec 8th, 2019
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.68 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstddef>
  3. #include <ctime>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <bits/ios_base.h>
  7. #include <iostream>
  8. #include <random>
  9.  
  10. #define DEBUG
  11. #ifdef DEBUG
  12. #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  13. #else
  14. #define eprintf(...)
  15. #endif
  16.  
  17.  
  18. using namespace std;
  19.  
  20. const long long INF = 8e18 + 1;
  21.  
  22. struct Point {
  23.     long long x;
  24.     long long y;
  25. };
  26.  
  27. struct Res {
  28.     Point a;
  29.     Point b;
  30.     long long d = INF;
  31. };
  32.  
  33.  
  34. long long dist(const Point &first, const Point &second) {
  35.     return (first.x - second.x) * (first.x - second.x) +
  36.            (first.y - second.y) * (first.y - second.y);
  37. }
  38.  
  39. vector<Point>
  40. strip(const Point &p, long long d, const vector<Point> &points, int left,
  41.       int right) {
  42.     vector<Point> res;
  43.     for (int i = left; i < right; i++) {
  44.         long long cur_d = (p.x - points[i].x) * (p.x - points[i].x);
  45.         if (cur_d < d) {
  46.             res.push_back(points[i]);
  47.         }
  48.     }
  49.     return res;
  50. }
  51.  
  52. void closest(const vector<Point> &points, Res &res) {
  53.     long long min_dist = res.d;
  54.     int a = -1, b = -1;
  55.     for (int i = 0; i < points.size(); i++) {
  56.         for (int j = i + 1; j < points.size()
  57.                             && (points[i].y - points[j].y) *
  58.                                (points[i].y - points[j].y) <
  59.                                min_dist; j++) {
  60.             long long cur_dist = dist(points[i], points[j]);
  61.             if (cur_dist < min_dist) {
  62.                 min_dist = cur_dist;
  63.                 a = i;
  64.                 b = j;
  65.             }
  66.         }
  67.     }
  68.     if (a != -1 && b != -1) {
  69.         res.a = points[a];
  70.         res.b = points[b];
  71.         res.d = min_dist;
  72.     }
  73. }
  74.  
  75.  
  76. Res brute_force(const vector<Point> &points, int left, int right) {
  77.     Res res = Res();
  78.     for (int i = left; i < right; i++) {
  79.         for (int j = i + 1; j < right; j++) {
  80.             long long d = dist(points[i], points[j]);
  81.             if (res.d > d) {
  82.                 res.d = d;
  83.                 res.a = points[i];
  84.                 res.b = points[j];
  85.             }
  86.         }
  87.     }
  88.     return res;
  89. }
  90.  
  91.  
  92. Res divide_and_conquer(const vector<Point> &points, int left, int right) {
  93.     if (right - left <= 3) {
  94.         return brute_force(points, left, right);
  95.     }
  96.     int m = (left + right) / 2;
  97.     Res left_res = divide_and_conquer(points, left, m);
  98.     Res right_res = divide_and_conquer(points, m, right);
  99.     long long d = min(left_res.d, right_res.d);
  100.     auto strip_points = strip(points[m], d, points, left, right);
  101.     sort(strip_points.begin(), strip_points.end(),
  102.          [](const Point &a, const Point &b) -> bool {
  103.              return a.y > b.y;
  104.          });
  105.     Res res = left_res.d < right_res.d ? left_res : right_res;
  106.     closest(strip_points, res);
  107.     return res;
  108. }
  109.  
  110. void stress_test() {
  111.     std::random_device rd;
  112.     std::mt19937_64 gen(rd());
  113.     std::uniform_int_distribution<long long> dis;
  114.  
  115.     while (true) {
  116.         int n = abs(rand() % 50000) + 2;
  117.         vector<Point> points;
  118.         for (int i = 0; i < n; i++) {
  119.             long long x = dis(gen) % 1000000000;
  120.             long long y = dis(gen) % 1000000000;
  121.             points.push_back({x, y});
  122.         }
  123.         sort(points.begin(), points.end(),
  124.              [](const Point &a, const Point &b) -> bool {
  125.                  return a.x > b.x;
  126.              });
  127.         Res expected = brute_force(points, 0, n);
  128.         Res actual = divide_and_conquer(points, 0, n);
  129.         if (expected.d != actual.d) {
  130.             eprintf("Got wrong res:\nexpected: %d %d, %d %d, %d\nactual: %d %d, %d %d, %d\n",
  131.                     (int) expected.a.x, (int) expected.a.y, (int) expected.b.x,
  132.                     (int) expected.b.y, (int) expected.d,
  133.                     (int) actual.a.x, (int) actual.a.y, (int) actual.b.x,
  134.                     (int) actual.b.y, (int) actual.d);
  135.             eprintf("%d\n", n);
  136.             for (auto &point : points) {
  137.                 eprintf("%d %d\n", (int) point.x, (int) point.y);
  138.             }
  139.             return;
  140.         } else {
  141.             eprintf("ok %d\n", n);
  142.         }
  143.     }
  144. }
  145.  
  146. int main() {
  147.     ios_base::sync_with_stdio(false);
  148.     cin.tie(0);
  149.     vector<Point> points;
  150.     //stress_test();
  151.     int n;
  152.  
  153.     cin >> n;
  154.     for (int i = 0; i < n; i++) {
  155.         long long x, y;
  156.         cin >> x >> y;
  157.         points.push_back({x, y});
  158.     }
  159.     sort(points.begin(), points.end(),
  160.          [](const Point &a, const Point &b) -> bool {
  161.              return a.x > b.x;
  162.          });
  163.     auto res = divide_and_conquer(points, 0, n);
  164.     //auto res = brute_force(points, 0, n);
  165.     cout << res.a.x << " " << res.a.y << " " << res.b.x << " " << res.b.y;
  166.  
  167. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement