Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <bits/stdc++.h>
- using namespace std;
- const int INF = 1e9;
- int main()
- {
- freopen("unionday.in", "r", stdin);
- freopen("unionday.out", "w", stdout);
- int n; cin >> n;
- double g[n][n];
- //g.resize(n);
- //for (int i = 0;i < n; i++) g[i].resize(n);
- vector <pair <int, int> > point(n);
- for (int i = 0; i < n; i++){
- int x,y; scanf("%d %d", &x, &y);
- point[i] = make_pair(x, y);
- }
- for (int i = 0; i < n; i++){
- for (int j = 0; j < n; j++){
- double cost = ((point[i].first - point[j].first)*(point[i].first - point[j].first) + (point[i].second - point[j].second) * (point[i].second - point[j].second));
- g[i][j] = cost;
- g[j][i] = cost;
- }
- }
- vector <bool> used(n);
- vector <int> min_edge(n, INF), end_edge(n, -1);
- min_edge[0] = 0;
- double ans = 0;
- for (int i = 0; i < n; i++){
- int v = -1;
- for (int j = 0; j < n; j++)
- if (!used[j] && (v == -1 || min_edge[j] < min_edge[v]))
- v = j;
- used[v] = 1;
- if (end_edge[v] != -1) ans += sqrtl(g[v][end_edge[v]]);
- for (int to = 0; to < n; to++)
- if (g[v][to] < min_edge[to]){
- min_edge[to] = g[v][to];
- end_edge[to] = v;
- }
- }
- printf("%f", ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement