Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int INF = int(1e9);
- int n;
- vector <int> x, y;
- vector <vector <long double> > gr;
- vector <bool> used;
- vector <int> min_e, sel_e;
- int main() {
- cin >> n;
- x.resize(n); y.resize(n);
- gr.resize(n, vector <long double> (n));
- min_e.assign(n, INF); sel_e.assign(n, -1);
- used.assign(n, 0);
- for (int i = 0; i < n; i++) {
- cin >> x[i] >> y[i];
- }
- long 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_e[j] < min_e[v]))
- v = j;
- }
- if (sel_e[v] != -1)
- ans += sqrt((x[v] - x[sel_e[v]]) * (x[v] - x[sel_e[v]]) + (y[v] - y[sel_e[v]]) * (y[v] - y[sel_e[v]]));
- used[v] = true;
- for (int to = 0; to < n; to++) {
- if (sqrt((x[v] - x[to]) * (x[v] - x[to]) + (y[v] - y[to]) * (y[v] - y[to])) < min_e[to]) {
- min_e[to] = sqrt((x[v] - x[to]) * (x[v] - x[to]) + (y[v] - y[to]) * (y[v] - y[to]));
- sel_e[to] = v;
- }
- }
- }
- cout << fixed << setprecision(15) << ans;
- return 0;
- }
Add Comment
Please, Sign In to add comment