Advertisement
ke_timofeeva7

прима с говном(координатами)

Mar 23rd, 2021
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.25 KB | None | 0 0
  1. /*
  2. ────────▄──────────────▄
  3. ────────▌▒█───────────▄▀▒▌
  4. ────────▌▒▒▀▄───────▄▀▒▒▒▐
  5. ───────▐▄▀▒▒▀▀▀▀▄▄▄▀▒▒▒▒▒▐
  6. ─────▄▄▀▒▒▒▒▒▒▒▒▒▒▒█▒▒▄█▒▐
  7. ───▄▀▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▀██▀▒▌
  8. ──▐▒▒▒▄▄▄▒▒▒▒▒▒▒▒▒▒▒▒▒▀▄▒▒▌
  9. ──▌▒▒▐▄█▀▒▒▒▒▄▀█▄▒▒▒▒▒▒▒█▒▐
  10. ─▐▒▒▒▒▒▒▒▒▒▒▒▌██▀▒▒▒▒▒▒▒▒▀▄▌
  11. ─▌▒▀▄██▄▒▒▒▒▒▒▒▒▒▒▒░░░░▒▒▒▒▌
  12. _▌▀▐▄█▄█▌▄▒▀▒▒▒▒▒▒░░░░░░▒▒▒▐
  13. ▐▒▀▐▀▐▀▒▒▄▄▒▄▒▒▒▒▒░░░░░░▒▒▒▒▌
  14. ▐▒▒▒▀▀▄▄▒▒▒▄▒▒▒▒▒▒░░░░░░▒▒▒▐
  15. ─▌▒▒▒▒▒▒▀▀▀▒▒▒▒▒▒▒▒░░░░▒▒▒▒▌
  16. ─▐▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▐
  17. ──▀▄▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▄▒▒▒▒▌
  18. ────▀▄▒▒▒▒▒▒▒▒▒▒▄▄▄▀▒▒▒▒▄▀
  19. ───▐▀▒▀▄▄▄▄▄▄▀▀▀▒▒▒▒▒▄▄▀
  20. ──▐▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▀▀
  21. */
  22.  
  23.  
  24. #include <iostream>
  25. #include <string>
  26. #include <sstream>
  27. #include <cmath>
  28. #include <algorithm>
  29. #include <memory.h>
  30. #include <stdio.h>
  31. #include <vector>
  32. #include <stack>
  33. #include <deque>
  34. #include <queue>
  35. #include <vector>
  36. #include <set>
  37. #include <iterator>
  38. #include <map>
  39. #include <iomanip>
  40. //#define int long long
  41. #define fir first
  42. #define sec second
  43. #define pb push_back
  44. //#define double long double
  45. #define endl "\n"
  46. #define un unsigned
  47. #define INF 1000000000
  48. using namespace std;
  49.  
  50. pair<int, int> koor[7000];
  51.  
  52. int dist(int i, int j)
  53. {
  54.     return (koor[i].first - koor[j].fir) * (koor[i].first - koor[j].fir) + (koor[i].sec - koor[j].sec) * (koor[i].sec - koor[j].sec);
  55. }
  56.  
  57. signed main()
  58. {
  59.     ios_base::sync_with_stdio(0);
  60.     cin.tie(0);
  61.     cout.tie(0);
  62.  
  63.     int n;
  64.     cin >> n;
  65.  
  66.     for (int i = 0; i < n; i++)
  67.     {
  68.         int a, b;
  69.         cin >> a >> b;
  70.  
  71.         koor[i] = { a, b };
  72.     }
  73.  
  74.     vector<int> min_e(n, INF); // вес минимального ребра из чёрной вершины в любую зелёную
  75.     vector<int> sel_e(n, -1); // куда ведёт ^ минимальное ребро из чёрной вершины в зелёную
  76.     vector<int> used(n, 0); // зeлeные вершины
  77.  
  78.     double mst = 0;
  79.     min_e[1] = 0;
  80.  
  81.     for (int i = 0; i < n; i++)
  82.     {
  83.         int v = -1;
  84.  
  85.         for (int j = 0; j < n; j++)
  86.         {
  87.             if (!used[j] && (v == -1 || min_e[j] < min_e[v]))
  88.                 v = j;
  89.         }
  90.        
  91.         used[v] = 1;
  92.  
  93.         if (sel_e[v] != -1)
  94.         {
  95.             mst += sqrt((double) dist(v, sel_e[v]));
  96.         }
  97.  
  98.         for (int j = 0; j < n; j++)
  99.         {
  100.             int kek = dist(v, j);
  101.  
  102.             if (used[j] == 0 && kek < min_e[j])
  103.             {
  104.                 min_e[j] = kek;
  105.                 sel_e[j] = v;
  106.             }
  107.         }
  108.     }
  109.  
  110.     cout.precision(17);
  111.  
  112.     cout << fixed << mst;
  113.  
  114.     return 0;
  115. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement