Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cmath>
- const long double inf = 10000000000;
- struct Agent
- {
- long double x;
- long double y;
- };
- long double dist(Agent A, Agent B)
- {
- long double x = A.x - B.x;
- long double y = A.y - B.y;
- return sqrt(x * x + y * y);
- }
- int main()
- {
- int n;
- std::cin >> n;
- std::vector<struct Agent> agents(n);
- std::vector<std::vector<long double> > dist_matrix(n, std::vector<long double>(n));
- for (int i = 0; i < n; ++i)
- std::cin >> agents[i].x >> agents[i].y;
- for (int i = 0; i < n; ++i)
- for (int j = i + 1; j < n; ++j)
- {
- long double d = dist(agents[i], agents[j]);
- dist_matrix[i][j] = d;
- dist_matrix[j][i] = d;
- }
- std::vector<bool> is_used(n);
- std::vector<long double> min_length_to_tree(n, inf);
- min_length_to_tree[0] = 0;
- long double R = 0;
- for (int i = 0; i < n; ++i)
- {
- int best_vertex = -1;
- for (int j = 0; j < n; ++j)
- if (!is_used[j]
- && (best_vertex == -1 || min_length_to_tree[j] < min_length_to_tree[best_vertex]))
- best_vertex = j;
- if (R < min_length_to_tree[best_vertex])
- R = min_length_to_tree[best_vertex];
- is_used[best_vertex] = true;
- for (int k = 0; k < n; ++k)
- if (dist_matrix[best_vertex][k] < min_length_to_tree[k])
- min_length_to_tree[k] = dist_matrix[best_vertex][k];
- }
- std::cout.setf(std::ios::fixed);
- std::cout.precision(10);
- std::cout << R;
- return 0;
- }
Add Comment
Please, Sign In to add comment