• API
• FAQ
• Tools
• Archive
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 = 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.

Top