Advertisement
Guest User

Untitled

a guest
Jun 22nd, 2022
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.85 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define speed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  6. #define pb push_back
  7. #define mp make_pair                                
  8. #define F first
  9. #define S second
  10. #define sz(x) (int)(x.size())                        
  11. #define all(x) x.begin(), x.end()        
  12.  
  13. typedef long long ll;
  14. typedef unsigned long long ull;
  15.  
  16.  
  17. const ll INF = LLONG_MAX;
  18. const int inf = INT_MAX;
  19. const int N = 5005;
  20. const ll MOD = 1e9+7;
  21. const double EPS = 1e-9;                
  22.  
  23. short int p[N], r[N];
  24.  
  25. void make_set(short int v){
  26.     p[v] = v;
  27.     r[v] = 1;
  28. }
  29.  
  30. short int find_set(short int v){
  31.     if(p[v] == v)
  32.         return v;
  33.     return p[v] = find_set(p[v]);
  34. }
  35.  
  36. void union_sets(short int u, short int v){
  37.     u = find_set(u);
  38.     v = find_set(v);
  39.     if(u == v)
  40.         return;
  41.     if(r[u] < r[v])
  42.         swap(u, v);
  43.     p[v] = u;
  44.     if(r[u] == r[v])
  45.         r[u]++;
  46. }
  47.  
  48. struct edge{
  49.     short int u, v;
  50.     int w;
  51. };
  52.  
  53. struct cor{
  54.     short int x, y;
  55. };
  56.  
  57. bool cmp(edge a, edge b){
  58.     return a.w < b.w;
  59. }
  60.  
  61.  
  62. vector <edge> edges;
  63. vector <cor> c;
  64.  
  65. void solve(){
  66.     short int n, x, y;      
  67.     double ans = 0;  
  68.     cin >> n;
  69.    
  70.     for(short int i = 1; i <= n; i++)
  71.         make_set(i);
  72.  
  73.     for(short int i = 1; i <= n; i++){
  74.         cin >> x >> y;
  75.         c.pb({x, y});
  76.     }
  77.  
  78.     for(short int i = 0; i < n; i++)
  79.         for(short int j = i+1; j < n; j++)
  80.             edges.pb({i + 1, j + 1, (int)(c[i].x - c[j].x) * (int)(c[i].x - c[j].x) + (int)(c[i].y-c[j].y) * (int)(c[i].y-c[j].y)});
  81.  
  82.     sort(all(edges), cmp);
  83.  
  84.     for(auto x : edges){
  85.         if(find_set(x.u) != find_set(x.v)){
  86.             union_sets(x.u, x.v);
  87.             ans += sqrt(x.w);
  88.         }
  89.     }
  90.     cout << fixed << setprecision(6) << '\n';;
  91.     cout << ans << '\n';
  92. }
  93.  
  94. int main(){
  95.     speed;
  96.    
  97.     freopen("unionday.in","r",stdin);
  98.     freopen("unionday.out","w",stdout);
  99.  
  100.     int T = 1;
  101.                  
  102.  
  103.     while(T--)
  104.         solve();
  105.  
  106.     return 0;
  107. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement