Advertisement
Guest User

odcinek

a guest
Apr 16th, 2018
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.17 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <algorithm>
  4. #include <utility>
  5. #include <vector>
  6. #include <cmath>
  7.  
  8. using namespace std;
  9.  
  10. typedef pair<int, int> punkt;
  11.  
  12. bool comp_x(const punkt &a, const punkt &b) {
  13.     return a.first < b.first;
  14. }
  15.  
  16. bool comp_y(const punkt &a, const punkt &b) {
  17.     return a.second < b.second;
  18. }
  19.  
  20. bool comp_x_y(const punkt &a, const punkt &b) {
  21.     return a.first == b.first ?
  22.         a.second < b.second : a.first < b.first;
  23. }
  24.  
  25. double odl(const punkt &a, const punkt &b) {
  26.     double dx = b.first - a.first, dy = b.second - a.second;
  27.     return sqrt((dx * dx) + (dy * dy));
  28. }
  29.  
  30. double min_odl(const vector<punkt> &t, int a, int b) {
  31.     if (b - a == 2) return odl(t[a], t[a+1]);
  32.     else if (b - a == 3) {
  33.         double p = odl(t[a], t[a+1]);
  34.         double q = odl(t[a], t[a+2]);
  35.         double r = odl(t[a+1], t[a+2]);
  36.         return min(min(p, q), r);
  37.     }
  38.     else
  39.     {
  40.         int c = (a + b) / 2;
  41.         double mdl = min_odl(t, a, c);
  42.         double mdr = min_odl(t, c, b);
  43.         double m = min(mdl, mdr);
  44.  
  45.         int mlx = int(ceil(t[c].first - m));
  46.         int aa = c;
  47.         for (int j = c - 1; j >= a; j--){
  48.             if (t[j].first < mlx) break;
  49.             else aa--;
  50.         }
  51.        
  52.  
  53.         int mrx = int(floor(t[c-1].first + m));
  54.         int bb = c;
  55.         for (int j = c ; j < b; j++){
  56.             if (t[j].first > mrx) break;
  57.             else bb++;
  58.         }
  59.        
  60.         double dm = m;
  61.         if (c - aa > 0 && bb - c > 0) {
  62.             vector<punkt> p(bb - aa);
  63.             copy(t.begin() + aa, t.begin() + bb, p.begin());
  64.             sort(p.begin(), p.end(), comp_y);
  65.             for (int u = 0, v = 1; v < p.size(); u++, v++){
  66.                 dm = min(odl(p[u], p[v]), dm);
  67.  
  68.             }
  69.         }
  70.         return dm;
  71.     }
  72. }
  73. int main() {
  74.     int n;
  75.     cin >> n;
  76.     vector<punkt> t;
  77.     for (int i = 0; i < n; i++) {
  78.         int x, y;
  79.         cin >> x >> y;
  80.         t.push_back(make_pair(x, y));
  81.     }
  82.     sort(t.begin(), t.end(), comp_x_y);
  83.     double d = min_odl(t, 0, n);
  84.  
  85.     cout << fixed << showpoint << setprecision(5) << d << endl;
  86.     return 0;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement