Advertisement
Stepavly

Untitled

Jul 16th, 2019
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.10 KB | None | 0 0
  1. #include <math.h>
  2. #include <iostream>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7.  
  8. const int INF = 1000000000;
  9.  
  10. struct pt
  11. {
  12. ll x, y;
  13. };
  14.  
  15. double dist(const pt& a, const pt& b)
  16. {
  17. return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
  18. }
  19.  
  20. int chosenV[5000];
  21. double minD[5000];
  22. char used[5000];
  23.  
  24. int main()
  25. {
  26. ios_base::sync_with_stdio(0);
  27. cin.tie(0);
  28. cout.setf(cout.fixed);
  29. cout.precision(12);
  30.  
  31. int n;
  32. cin >> n;
  33.  
  34. vector<pt> pts(n);
  35.  
  36. for (int i = 0; i < n; i++)
  37. {
  38. cin >> pts[i].x >> pts[i].y;
  39. }
  40.  
  41. fill(chosenV, chosenV + n, -1);
  42. fill(minD, minD + n, INF);
  43.  
  44. minD[0] = 0;
  45. double res = 0;
  46.  
  47. for (int i = 0; i < n; i++)
  48. {
  49. int v = -1;
  50.  
  51. for (int j = 0; j < n; j++)
  52. {
  53. if (!used[j] && (v == -1 || minD[v] > minD[j]))
  54. {
  55. v = j;
  56. }
  57. }
  58.  
  59. used[v] = 1;
  60.  
  61. if (chosenV[v] != -1)
  62. res += dist(pts[v], pts[chosenV[v]]);
  63.  
  64. for (int j = 0; j < n; j++)
  65. {
  66. if (minD[j] > dist(pts[v], pts[j]))
  67. {
  68. minD[j] = dist(pts[v], pts[j]);
  69. chosenV[j] = v;
  70. }
  71. }
  72. }
  73.  
  74. cout << res;
  75.  
  76. return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement