Advertisement
Guest User

Untitled

a guest
Apr 24th, 2018
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.31 KB | None | 0 0
  1. // Closest pair
  2.  
  3. #include <iostream>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <float.h>
  8. using namespace std;
  9.  
  10. struct Punt {
  11.   double x, y;
  12. };
  13.  
  14. double min(double x, double y) {
  15.   if (x < y) return x;
  16.   return y;
  17. }
  18.  
  19. bool comparadorX(const Punt& p1, const Punt& p2) {
  20.   if (p1.x != p2.x) return p1.x < p2.x;
  21.   return p1.y < p2.y;
  22. }
  23.  
  24. bool comparadorY(const Punt& p1, const Punt& p2) {
  25.   if (p1.y != p2.y) return p1.y < p2.y;
  26.   return p1.x < p2.x;
  27. }
  28.  
  29. double distancia(const Punt& p1, const Punt& p2) {
  30.   return sqrt((p2.x - p1.x)*(p2.x - p1.x) +
  31.               (p2.y - p1.y)*(p2.y - p1.y));
  32. }
  33.  
  34. double distancia_min(const vector<Punt>& v, int n) {
  35.   double dis;
  36.   double min = DBL_MAX;
  37.  
  38.   for (int i = 0; i < n; ++i)
  39.     for (int j = i+1; j < n; ++j) {
  40.       dis = distancia(v[i], v[j]);
  41.       if (dis < min) min = dis;
  42.     }
  43.   return min;
  44. }
  45.  
  46. double propers_tira(const vector<Punt>& tira, int n, double d) {
  47.   double dis;
  48.   double min = d;
  49.  
  50.   for (int i = 0; i < n; ++i)
  51.     for (int j = i+1; (j < n) and ((tira[j].y - tira[i].y) < min); ++j) {
  52.       dis = distancia(tira[i], tira[j]);
  53.       if (dis < min) min = dis;
  54.     }
  55.   return min;
  56. }
  57.  
  58. double closest(vector<Punt> vx, vector<Punt> vy, int n) {
  59.   if (n <= 3) return distancia_min(vx, n);
  60.  
  61.   int mig = n / 2;
  62.   Punt puntMig = vx[mig];
  63.  
  64.   vector<Punt> vy_esquerra(mig+1);
  65.   vector<Punt> vy_dreta(n-mig-1);
  66.  
  67.   int esq = 0, dre = 0;
  68.   for (int i = 0; i < n; ++i) {
  69.     if (vy[i].x <= puntMig.x) vy_esquerra[esq++] = vy[i];
  70.     else vy_dreta[dre++] = vy[i];
  71.   }
  72.  
  73.   double d_esq = closest(vx, vy_esquerra, mig);
  74.   double d_dre = closest(vx, vy_dreta, n-mig);
  75.   double d = min(d_esq, d_dre);
  76.  
  77.   vector<Punt> tira(n);
  78.   int j = 0;
  79.   for (int i = 0; i < n; ++i)
  80.     if (abs(vy[i].x - puntMig.x) < d) {
  81.       tira[j] = vy[i];
  82.       j++;
  83.     }
  84.  
  85.   return min(d, propers_tira(tira, j, d));
  86. }
  87.  
  88. double closestPair(const vector<Punt>& v, int n) {
  89.   vector<Punt> vx = v;
  90.   vector<Punt> vy = v;
  91.  
  92.   sort(vx.begin(), vx.end(), comparadorX);
  93.   sort(vy.begin(), vy.end(), comparadorY);
  94.  
  95.   return closest(vx, vy, n);
  96. }
  97.  
  98. int main() {
  99.   cout.setf(ios::fixed);
  100.   cout.precision(5);
  101.  
  102.   double x, y;
  103.   vector<Punt> v;
  104.   while (cin >> x >> y)
  105.     v.push_back({x, y});
  106.  
  107.   cout << closestPair(v, v.size()) << endl;
  108. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement