KShah

Untitled

Jul 4th, 2020
308
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.19 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int INF = int(1e9);
  5. int n;
  6. vector <int> x, y;
  7. vector <vector <long double> > gr;
  8. vector <bool> used;
  9. vector <int> min_e, sel_e;
  10.  
  11. int main() {
  12.     cin >> n;
  13.     x.resize(n); y.resize(n);
  14.     gr.resize(n, vector <long double> (n));
  15.     min_e.assign(n, INF); sel_e.assign(n, -1);
  16.     used.assign(n, 0);
  17.  
  18.     for (int i = 0; i < n; i++) {
  19.         cin >> x[i] >> y[i];
  20.     }
  21.  
  22.     long double ans = 0;
  23.     for (int i = 0; i < n; ++i) {
  24.         int v = -1;
  25.  
  26.         for (int j = 0; j < n; ++j) {
  27.             if(!used[j] && (v == -1 || min_e[j] < min_e[v]))
  28.                 v = j;
  29.         }
  30.         if (sel_e[v] != -1)
  31.             ans += sqrt((x[v] - x[sel_e[v]]) * (x[v] - x[sel_e[v]]) + (y[v] - y[sel_e[v]]) * (y[v] - y[sel_e[v]]));
  32.         used[v] = true;
  33.         for (int to = 0; to < n; to++) {
  34.             if (sqrt((x[v] - x[to]) * (x[v] - x[to]) + (y[v] - y[to]) * (y[v] - y[to])) < min_e[to]) {
  35.                 min_e[to] = sqrt((x[v] - x[to]) * (x[v] - x[to]) + (y[v] - y[to]) * (y[v] - y[to]));
  36.                 sel_e[to] = v;
  37.             }
  38.         }
  39.     }
  40.     cout << fixed << setprecision(15) << ans;
  41.     return 0;
  42. }
Add Comment
Please, Sign In to add comment