SHARE
TWEET

Untitled

Stepavly Jul 16th, 2019 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <math.h>
  2. #include <iostream>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7.  
  8. const int INF = 1000000000;
  9.  
  10. struct pt
  11. {
  12.     ll x, y;
  13. };
  14.  
  15. double dist(const pt& a, const pt& b)
  16. {
  17.     return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
  18. }
  19.  
  20. int chosenV[5000];
  21. double minD[5000];
  22. char used[5000];
  23.  
  24. int main()
  25. {
  26.     ios_base::sync_with_stdio(0);
  27.     cin.tie(0);
  28.     cout.setf(cout.fixed);
  29.     cout.precision(12);
  30.    
  31.     int n;
  32.     cin >> n;
  33.  
  34.     vector<pt> pts(n);
  35.  
  36.     for (int i = 0; i < n; i++)
  37.     {
  38.         cin >> pts[i].x >> pts[i].y;
  39.     }
  40.  
  41.     fill(chosenV, chosenV + n, -1);
  42.     fill(minD, minD + n, INF);
  43.  
  44.     minD[0] = 0;
  45.     double res = 0;
  46.  
  47.     for (int i = 0; i < n; i++)
  48.     {
  49.         int v = -1;
  50.  
  51.         for (int j = 0; j < n; j++)
  52.         {
  53.             if (!used[j] && (v == -1 || minD[v] > minD[j]))
  54.             {
  55.                 v = j;
  56.             }
  57.         }
  58.  
  59.         used[v] = 1;
  60.  
  61.         if (chosenV[v] != -1)
  62.             res += dist(pts[v], pts[chosenV[v]]);
  63.  
  64.         for (int j = 0; j < n; j++)
  65.         {
  66.             if (minD[j] > dist(pts[v], pts[j]))
  67.             {
  68.                 minD[j] = dist(pts[v], pts[j]);
  69.                 chosenV[j] = v;
  70.             }
  71.         }
  72.     }
  73.  
  74.     cout << res;
  75.  
  76.     return 0;
  77. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top