Advertisement
skimono

Untitled

Aug 5th, 2021
236
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.74 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include <iostream>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <iomanip>
  8. #include <fstream>
  9. #include <string>
  10. #include <set>
  11. #include <deque>
  12. #include <queue>
  13. #include <map>
  14. #include <bitset>
  15. #include <random>
  16.  
  17. using namespace std;
  18.  
  19. typedef int ll;
  20. typedef unsigned long long ull;
  21. typedef double ld;
  22. #define endl "\n"
  23.  
  24. #define all(a) a.begin(), a.end();
  25.  
  26. const ll inf = 1e9;
  27. long double eps = 1e-9;
  28. const ll maxsz = 5001;
  29. pair<ll, ll> a[maxsz];
  30. vector <pair <ll, ld> > gr[maxsz];
  31.  
  32. ld getl(ll x1, ll y1, ll x2, ll y2) {
  33.     return sqrt(((x1 - x2) * (x1 - x2)) + ((y1 - y2) * (y1 - y2)));
  34. }
  35.  
  36. signed main() {
  37. #ifdef _DEBUG
  38.     freopen("input.txt", "r", stdin);
  39.     freopen("output.txt", "w", stdout);
  40. #endif
  41.     ios_base::sync_with_stdio(0);
  42.     cin.tie(NULL);
  43.     cout.tie(NULL);
  44.     ll n, i, j;
  45.     cin >> n;
  46.     for (i = 0; i < n; i++) {
  47.         cin >> a[i].first >> a[i].second;
  48.     }
  49.     for (i = 0; i < n; i++) {
  50.         for (j = i + 1; j < n; j++) {
  51.             gr[i].push_back({ j,getl(a[i].first, a[i].second, a[j].first, a[j].second) });
  52.             gr[j].push_back({ i,getl(a[i].first, a[i].second, a[j].first, a[j].second) });
  53.         }
  54.     }
  55.     vector <ld> d(n, inf);
  56.     vector <bool> used(n, false);
  57.     d[0] = 0;
  58.     ld ans = 0;
  59.     for (i = 0; i < n; i++) {
  60.         ll v = -1;
  61.         for (ll u = 0; u < n; u++) {
  62.             if (!used[u] && (v == -1 || d[v] > d[u])) {
  63.                 v = u;
  64.             }
  65.         }
  66.         used[v] = true;
  67.         ans += d[v];
  68.         for (auto [u, w] : gr[v]) {
  69.             if (d[u] > w) {
  70.                 d[u] = w;
  71.             }
  72.         }
  73.     }
  74.     cout << fixed << setprecision(10)
  75.         << ans;
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement