vadimk772336

принята

Nov 19th, 2021 (edited)
174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.62 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4.  
  5. const long double inf = 10000000000;
  6.  
  7. struct Agent
  8. {
  9.     long double x;
  10.     long double y;
  11. };
  12.  
  13. long double dist(Agent A, Agent B)
  14. {
  15.     long double x = A.x - B.x;
  16.     long double y = A.y - B.y;
  17.     return sqrt(x * x + y * y);
  18. }
  19.  
  20. int main()
  21. {
  22.     int n;
  23.     std::cin >> n;
  24.     std::vector<struct Agent> agents(n);
  25.     std::vector<std::vector<long double> > dist_matrix(n, std::vector<long double>(n));
  26.  
  27.     for (int i = 0; i < n; ++i)
  28.         std::cin >> agents[i].x >> agents[i].y;
  29.  
  30.     for (int i = 0; i < n; ++i)
  31.         for (int j = i + 1; j < n; ++j)
  32.         {
  33.             long double d = dist(agents[i], agents[j]);
  34.             dist_matrix[i][j] = d;
  35.             dist_matrix[j][i] = d;
  36.         }
  37.  
  38.  
  39.     std::vector<bool> is_used(n);
  40.     std::vector<long double> min_length_to_tree(n, inf);
  41.  
  42.     min_length_to_tree[0] = 0;
  43.     long double R = 0;
  44.  
  45.     for (int i = 0; i < n; ++i)
  46.     {
  47.         int best_vertex = -1;
  48.         for (int j = 0; j < n; ++j)
  49.             if (!is_used[j]
  50.                 && (best_vertex == -1 || min_length_to_tree[j] < min_length_to_tree[best_vertex]))
  51.                 best_vertex = j;
  52.  
  53.         if (R < min_length_to_tree[best_vertex])
  54.             R = min_length_to_tree[best_vertex];
  55.  
  56.         is_used[best_vertex] = true;
  57.         for (int k = 0; k < n; ++k)
  58.             if (dist_matrix[best_vertex][k] < min_length_to_tree[k])
  59.                 min_length_to_tree[k] = dist_matrix[best_vertex][k];
  60.     }
  61.  
  62.     std::cout.setf(std::ios::fixed);
  63.     std::cout.precision(10);
  64.  
  65.     std::cout << R;
  66.     return 0;
  67. }
  68.  
Add Comment
Please, Sign In to add comment