Advertisement
Guest User

Untitled

a guest
Mar 29th, 2020
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.28 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. using namespace std;
  4.  
  5. const int INT_MAX = 100000000;
  6.  
  7. class Point
  8. {
  9. public:
  10. int x = 0, y = 0;
  11. double len2p(const Point& B)
  12. {
  13. return sqrt((B.x - x) * (B.x - x) + (B.y - y) * (B.y - y));
  14. };
  15. };
  16.  
  17. int main()
  18. {
  19. freopen("spantree.in","r",stdin);
  20. freopen("spantree.out","w",stdout);
  21. int n, x, y;
  22. double res = 0;
  23. cin >> n;
  24.  
  25. Point buff[n];
  26. int vis[n];
  27. double edges[n];
  28.  
  29. for (int i = 0; i < n; i++)
  30. {
  31. cin >> x >> y;
  32. buff[i] = Point{x, y};
  33. vis[i] = 0;
  34. if (i > 0) edges[i] = buff[0].len2p(buff[i]);
  35. }
  36. vis[0] = 1;
  37.  
  38.  
  39. for (int j = 1; j < n; j++)
  40. {
  41. double minLen = INT_MAX;
  42. int help = 0;
  43. for(int i = 1; i < n; i++)
  44. if (edges[i] < minLen && !vis[i])
  45. {
  46. minLen = edges[i];
  47. help = i;
  48. }
  49. vis[help] = 1;
  50. res += minLen;
  51. for (int i = 0; i < n; i++)
  52. {
  53. if (!vis[i])
  54. {
  55. double len = buff[help].len2p(buff[i]);
  56. if (len < edges[i]) edges[i] = len;
  57. }
  58. }
  59. }
  60. cout << res << "\n";
  61. return 0;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement