Advertisement
Guest User

Untitled

a guest
Mar 23rd, 2019
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.48 KB | None | 0 0
  1.  
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <bitset>
  6. #include <set>
  7. #include <cmath>
  8.  
  9. using namespace std;
  10.  
  11. const int INF = 1000000000;
  12. double eucl_dist[5000][5000];
  13. //vector<vector<double>> eucl_dist;
  14. int coord_x[5001], coord_y[5001];
  15. bool used[5000];
  16. //vector<bool> used;
  17. //vector<double> dist;
  18.  
  19.  
  20. int main() {
  21.     ios_base::sync_with_stdio(false);
  22.     cin.tie(0);
  23.     int n;
  24.     cin >> n;
  25.    
  26.     vector<int> dist (n, INF);
  27.    
  28.     for (int i = 0; i < n; i++) {
  29.         cin >> coord_x[i] >> coord_y[i];
  30.     }
  31.    
  32.     for (int i = 0; i < n; i++) {
  33.         for (int j = 0; j < n; j++) {
  34.             int d_x = coord_x[i] - coord_x[j];
  35.             int d_y = coord_y[i] - coord_y[j];
  36.             eucl_dist[i][j] = d_x * d_x + d_y * d_y;
  37.         }
  38.     }
  39.    
  40.     double answer_w = 0;
  41.     dist[0] = 0;
  42.    
  43.     for (int i = 0; i < n; i++) {
  44.         //int v = -1;
  45.        
  46.         double min = INF;
  47.         int min_index;
  48.         for (int v = 0; v < n; v++) {
  49.             if (!used[v] && dist[v] < min) {
  50.                 min = dist[v];
  51.                 min_index = v;
  52.             }
  53.         }
  54.         int u = min_index;
  55.         used[u] = true;
  56.         answer_w += sqrt(dist[u]);
  57.        
  58.         for (int v = 0; v < n; v++) {
  59.             if (eucl_dist[u][v] < dist[v]) {
  60.                 dist[v] = eucl_dist[u][v];
  61.             }
  62.         }
  63.     }
  64.    
  65.     cout.precision(9);
  66.     cout << answer_w << "\n";
  67.    
  68.     return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement