Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long double ld;
- const unsigned int INF = 1e8;
- struct tt
- {
- int x, y;
- };
- #define sqr(a) pow(a, 2)
- int main()
- {
- unsigned int n;
- cin >> n;
- vector <tt> a(n);
- vector<vector <unsigned int> > g(n);
- for (int i = 0; i < n; i++)
- cin >> a[i].x >> a[i].y;
- for (int i = 0; i < n; i++)
- for (int j = 0; j < n; j++)
- {
- if (i != j)
- g[i].push_back(sqr(a[i].x - a[j].x) + sqr(a[i].y - a[j].y));
- else
- g[i].push_back(INF);
- }
- vector<bool> used (n, false);
- vector<int> min_e (n, INF), sel_e (n, -1);
- min_e[0] = 0;
- for (int i=0; i<n; ++i) {
- int v = -1;
- for (int j=0; j<n; ++j)
- if (!used[j] && (v == -1 || min_e[j] < min_e[v]))
- v = j;
- used[v] = true;
- for (int to=0; to<n; ++to)
- if (g[v][to] < min_e[to] && !used[to]) { //2
- min_e[to] = g[v][to];
- sel_e[to] = v;
- }
- }
- ld ans = 0;
- for (int i = 1; i < n; i++)
- {
- //cout << a[i].x << " " << a[i].y << " " << a[sel_e[i]].x << " " << a[sel_e[i]].y << endl;
- ans += sqrt(sqr(a[i].x - a[sel_e[i]].x) + sqr(a[i].y - a[sel_e[i]].y));
- }
- cout << setprecision(7) << fixed << ans << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement