ProgMe

Untitled

Dec 24th, 2023
846
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.47 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int int64_t
  3.  
  4. #pragma GCC optimize("O3")
  5.  
  6. using namespace std;
  7.  
  8. inline int sqr(int x) {
  9.     return x * x;
  10. }
  11.  
  12. inline int dist(pair<int, int> x, pair<int, int> y) {
  13.     return sqrt(sqr(x.first - y.first) + sqr(x.second - y.second));
  14. }
  15.  
  16. inline int bruteSolution(vector<pair<int, int>>& v) {
  17.     int ans = LLONG_MAX;
  18.     for (int i = 0; i < v.size(); i++) {
  19.         for (int j = i + 1; j < v.size() && j - i < 4; j++) {
  20.             ans = min(ans, dist(v[i], v[j]));
  21.         }
  22.     }
  23.     return ans;
  24. }
  25.  
  26. int calculateAnswer(vector<pair<int, int>>& v, int l, int r) {
  27.     if (l == r) {
  28.         return LLONG_MAX;
  29.     }
  30.  
  31.     int m = (l + r) / 2;
  32.     int middle_x = v[m].first;
  33.  
  34.     int answer = min(calculateAnswer(v, l, m), calculateAnswer(v, m + 1, r));
  35.  
  36.     for (int i = l, j = m + 1; i <= m && j <= r;) {
  37.         if (v[i] <= v[j]) {
  38.             i++;
  39.         } else {
  40.             swap(v[i], v[j++]);
  41.         }
  42.     }
  43.  
  44.     vector<pair<int, int>> check;
  45.  
  46.     for (int i = l; i <= r; i++) {
  47.         if (abs(v[i].first - middle_x) <= answer) {
  48.             check.push_back(v[i]);
  49.         }
  50.     }
  51.  
  52.     return min(answer, bruteSolution(check));
  53. }
  54.  
  55. int32_t main() {
  56.     ios::sync_with_stdio(false);
  57.     cin.tie(nullptr);
  58.  
  59.     vector<pair<int, int>> pts;
  60.  
  61.     int x, y;
  62.     while (cin >> x >> y) {
  63.         pts.emplace_back(x, y);
  64.     }
  65.     sort(pts.begin(), pts.end());
  66.  
  67.     cout << calculateAnswer(pts, 0, pts.size() - 1);
  68. }
  69.  
Advertisement
Add Comment
Please, Sign In to add comment