SHARE
TWEET

Untitled

a guest Mar 24th, 2019 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <cmath>
  6. using namespace std;
  7.  
  8. const int N = 5010;
  9.  
  10. typedef pair<double, double> pdd;
  11. #define mp make_pair
  12. #define X first
  13. #define Y second
  14.  
  15. pdd a[N];
  16.  
  17. double sqr(double x)
  18. {
  19.     return x * x;
  20. }
  21.  
  22. double getDist(int v, int u)
  23. {
  24.     return sqrt(sqr(a[v].X - a[u].X) + sqr(a[v].Y - a[u].Y));
  25. }
  26. int n;
  27. bool u[N];
  28. int b[N];
  29.  
  30. double ans = 0.;
  31.  
  32. int main()
  33. {
  34.     freopen("unionday.in", "r", stdin);
  35.     freopen("unionday.out", "w", stdout);
  36.  
  37.     scanf("%d", &n);
  38.     for (int i = 0; i < n; i++)
  39.         scanf("%lf%lf", &a[i].X, &a[i].Y);
  40.    
  41.     u[0] = 1;
  42.     for (int i = 1; i < n; i++)
  43.         b[i] = 0;
  44.     for (int it = 1; it < n; it++)
  45.     {
  46.         int v = -1;
  47.         double t = 0.;
  48.         for (int i = 0; i < n; i++)
  49.         {
  50.             if (u[i]) continue;
  51.             if (v == -1 || t > getDist(i, b[i]))
  52.             {
  53.                 v = i;
  54.                 t = getDist(v, b[v]);
  55.             }
  56.         }
  57.         u[v] = 1;
  58.         ans += t;
  59.         for (int i = 0; i < n; i++)
  60.         {
  61.             if (u[i]) continue;
  62.             double w = getDist(v, i);
  63.             if (w < getDist(i, b[i]))
  64.                 b[i] = v;
  65.         }
  66.     }
  67.     printf("%.10lf\n", ans);
  68.  
  69.     return 0;
  70. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top