Advertisement
Dennnhhhickk

Untitled

Jul 1st, 2017
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.26 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long double ld;
  5. const unsigned int INF = 1e8;
  6. struct tt
  7. {
  8. int x, y;
  9. };
  10. #define sqr(a) pow(a, 2)
  11.  
  12. int main()
  13. {
  14. unsigned int n;
  15. cin >> n;
  16. vector <tt> a(n);
  17. vector<vector <unsigned int> > g(n);
  18. for (int i = 0; i < n; i++)
  19. cin >> a[i].x >> a[i].y;
  20. for (int i = 0; i < n; i++)
  21. for (int j = 0; j < n; j++)
  22. {
  23. if (i != j)
  24. g[i].push_back(sqr(a[i].x - a[j].x) + sqr(a[i].y - a[j].y));
  25. else
  26. g[i].push_back(INF);
  27. }
  28. vector<bool> used (n, false);
  29. vector<int> min_e (n, INF), sel_e (n, -1);
  30. min_e[0] = 0;
  31. for (int i=0; i<n; ++i) {
  32. int v = -1;
  33. for (int j=0; j<n; ++j)
  34. if (!used[j] && (v == -1 || min_e[j] < min_e[v]))
  35. v = j;
  36. used[v] = true;
  37.  
  38. for (int to=0; to<n; ++to)
  39. if (g[v][to] < min_e[to] && !used[to]) { //2
  40. min_e[to] = g[v][to];
  41. sel_e[to] = v;
  42. }
  43. }
  44. ld ans = 0;
  45. for (int i = 1; i < n; i++)
  46. {
  47. //cout << a[i].x << " " << a[i].y << " " << a[sel_e[i]].x << " " << a[sel_e[i]].y << endl;
  48. ans += sqrt(sqr(a[i].x - a[sel_e[i]].x) + sqr(a[i].y - a[sel_e[i]].y));
  49. }
  50. cout << setprecision(7) << fixed << ans << endl;
  51. return 0;
  52. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement