Advertisement
kolbka_

Untitled

Mar 12th, 2022
120
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.76 KB | None | 0 0
  1.  
  2.  
  3.  
  4. #include <unordered_map>
  5. #include <string>
  6. #include <vector>
  7. #include <iostream>
  8. #include <set>
  9. #include <queue>
  10. #include "optimization.h"
  11. #include <math.h>
  12. #include <unordered_map>
  13. #include <iomanip>
  14.  
  15. using namespace std;
  16. struct town {
  17.     int x;
  18.     int y;
  19. };
  20.  
  21.  
  22.  
  23.  
  24. int main() {
  25.     vector<tuple<double, int, int>> edges;
  26.     cout.tie(0);
  27.     cin.tie(0);
  28.     ios_base::sync_with_stdio(0);
  29.     int n = readInt();
  30. //    cin >> n;
  31.     vector<town> towns(n);
  32.     vector<int> id(n);
  33.     vector<vector<int>> sets(n);
  34.     for (int i = 0; i < n; i++) {
  35. //        cin >> towns[i].x >> towns[i].y;
  36.         towns[i].x = readInt(); towns[i].y = readInt();
  37.         id[i] = i;
  38.         sets[i].push_back(i);
  39.     }
  40.     unordered_map<int, double> used_x;
  41.     for (int i = 0; i < n; i++) {
  42.         for (int j = i + 1; j < n; j++) {
  43.             auto x1 = towns[i].x;
  44.             auto y1 = towns[i].y;
  45.             auto x2 = towns[j].x;
  46.             auto y2 = towns[j].y;
  47.             int x = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
  48.             if (used_x[x] == 0) {
  49.                 used_x[x] = sqrt(x);
  50.             }
  51.             edges.emplace_back(used_x[x], i, j);
  52.         }
  53.     }
  54.     double answer = 0;
  55.     sort(edges.begin(), edges.end());
  56.     for (auto[w, a, b]: edges) {
  57.         if (id[a] == id[b]) {
  58.             continue;
  59.         }
  60.         answer += w;
  61.  
  62.         int small = a;
  63.         if (sets[id[a]].size() > sets[id[b]].size()) {
  64.             small = b;
  65.         }
  66.         int big = a + b - small;
  67.         for (int x: sets[id[small]]) {
  68.             id[x] = id[big];
  69.             sets[id[big]].push_back(x);
  70.         }
  71.            
  72.  
  73.     }
  74. //    cout << std::setprecision(10) << answer;
  75.     writeDouble(answer, 10);
  76. }
  77.  
  78.  
  79.  
  80.  
  81.  
  82.  
  83.  
  84.  
  85.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement