Advertisement
Guest User

Untitled

a guest
Nov 20th, 2017
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.28 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <iomanip>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. vector<int> x, y;
  9.  
  10. int dist2(int i, int j) {
  11.     return (x[j] - x[i]) * (x[j] - x[i]) + (y[j] - y[i]) * (y[j] - y[i]);
  12. }
  13.  
  14. int main() {
  15.     freopen("unionday.in", "r", stdin);
  16.     freopen("unionday.out", "w", stdout);
  17.  
  18.     int n;
  19.     cin >> n;
  20.  
  21.     x.resize(static_cast<unsigned int>(n));
  22.     y.resize(static_cast<unsigned int>(n));
  23.     for (int i = 0; i < n; i++) {
  24.         cin >> x[i] >> y[i];
  25.     }
  26.  
  27.     double dist = 0;
  28.     vector<int> used(n, 0), min_e(n, static_cast<const int &>(1e9)), end_e(n, -1);
  29.  
  30.     min_e[0] = 0;
  31.     for (int i = 0; i < n; i++) {
  32.         int v = -1;
  33.         for (int j = 0; j < n; j++) {
  34.             if (!used[j] && (v == -1 || min_e[j] < min_e[v])) {
  35.                 v = j;
  36.             }
  37.         }
  38.  
  39.         used[v] = 1;
  40.         if (end_e[v] != -1) {
  41.             dist += sqrt((double) dist2(v, end_e[v]));
  42.         }
  43.  
  44.         for (int to = 0; to < n; to++) {
  45.             int next_dist = dist2(v, to);
  46.             if (!used[to] && next_dist < min_e[to]) {
  47.                 min_e[to] = next_dist;
  48.                 end_e[to] = v;
  49.             }
  50.         }
  51.     }
  52.  
  53.     cout << fixed << setprecision(5) << dist << '\n';
  54.     return 0;
  55.  
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement