Advertisement
Guest User

Untitled

a guest
Jun 22nd, 2022
150
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.78 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. int p[N], r[N];
  24.  
  25. void make_set(int v){
  26.     p[v] = v;
  27.     r[v] = 1;
  28. }
  29.  
  30. int find_set(int v){
  31.     if(p[v] == v)
  32.         return v;
  33.     return p[v] = find_set(p[v]);
  34. }
  35.  
  36. void union_sets(int u, 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.     int u, v, w;
  50. };
  51.  
  52. struct cor{
  53.     int x, y;
  54. };
  55.  
  56. bool cmp(edge a, edge b){
  57.     return a.w < b.w;
  58. }
  59.  
  60.  
  61. vector <edge> edges;
  62. vector <cor> c;
  63.  
  64. void solve(){
  65.     int n, x, y;      
  66.     double ans = 0;  
  67.     cin >> n;
  68.    
  69.     for(int i = 1; i <= n; i++)
  70.         make_set(i);
  71.  
  72.     for(int i = 1; i <= n; i++){
  73.         cin >> x >> y;
  74.         c.pb({x, y});
  75.     }
  76.  
  77.     for(int i = 0; i < n; i++)
  78.         for(int j = i+1; j < n; j++)
  79.             edges.pb({i + 1, j + 1, (c[i].x - c[j].x) * (c[i].x - c[j].x) + (c[i].y-c[j].y) * (c[i].y-c[j].y)});
  80.  
  81.     sort(all(edges), cmp);
  82.  
  83.     for(auto x : edges){
  84.         if(find_set(x.u) != find_set(x.v)){
  85.             union_sets(x.u, x.v);
  86.             ans += sqrt(x.w);
  87.         }
  88.     }
  89.     cout << fixed << setprecision(6) << '\n';;
  90.     cout << ans << '\n';
  91. }
  92.  
  93. int main(){
  94.     speed;
  95.    
  96.     freopen("unionday.in","r",stdin);
  97.     freopen("unionday.out","w",stdout);
  98.  
  99.     int T = 1;
  100.                  
  101.  
  102.     while(T--)
  103.         solve();
  104.  
  105.     return 0;
  106. }                                
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement