Advertisement
Josif_tepe

Untitled

Sep 28th, 2023
837
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.46 KB | None | 0 0
  1. #include <queue>
  2. #include <iostream>
  3. #include <vector>
  4. #include <cstring>
  5. #include <iostream>
  6. #include <set>
  7. #include <cstring>
  8. #include <stack>
  9. //#include <bits/stdc++.h>
  10. using namespace std;
  11. typedef long long ll;
  12. const int maxn = 3e5 + 10;
  13. const ll INF = 3e16 + 10;
  14.  
  15. int main() {
  16.     ios_base::sync_with_stdio(false);
  17.     int n;
  18.     cin >> n;
  19.     vector<pair<int, int>> points(n);
  20.    
  21.     for(int i = 0; i < n; i++) {
  22.         cin >> points[i].first >> points[i].second;
  23.     }
  24.     sort(points.begin(), points.end());
  25.     set<pair<int, int>> st;
  26.     st.insert(make_pair(points[0].first, points[0].second));
  27.     ll shortest_distance = 1e9, result = 1e18;
  28.     for(int i = 1; i < n; i++) {
  29.         set<pair<int, int>>::iterator it1 = st.lower_bound(make_pair(points[i].first - shortest_distance, points[i].second - shortest_distance));
  30.        
  31.         set<pair<int, int>>::iterator it2 = st.upper_bound(make_pair(points[i].first, points[i].second + shortest_distance));
  32.        
  33.         if(it1 == st.end()) {
  34.             continue;
  35.         }
  36.        
  37.         for(set<pair<int, int>>::iterator it = it1; it != it2; it++) {
  38.             ll dist = (points[i].first - it->first) * (points[i].first - it->first) + (points[i].second - it->second) * (points[i].second - it->second);
  39.             result = min(result, dist);
  40.         }
  41.         st.insert(make_pair (points[i].first, points[i].second));
  42.     }
  43.     cout << sqrt(result) << endl;
  44.     return 0;
  45. }
  46.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement