Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <cmath>
- #include <iomanip>
- #include <fstream>
- #include <string>
- #include <set>
- #include <deque>
- #include <queue>
- #include <map>
- #include <bitset>
- #include <random>
- using namespace std;
- typedef int ll;
- typedef unsigned long long ull;
- typedef double ld;
- #define endl "\n"
- #define all(a) a.begin(), a.end();
- const ll inf = 1e9;
- long double eps = 1e-9;
- const ll maxsz = 5001;
- pair<ll, ll> a[maxsz];
- vector <pair <ll, ld> > gr[maxsz];
- ld getl(ll x1, ll y1, ll x2, ll y2) {
- return sqrt(((x1 - x2) * (x1 - x2)) + ((y1 - y2) * (y1 - y2)));
- }
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(0);
- cin.tie(NULL);
- cout.tie(NULL);
- ll n, i, j;
- cin >> n;
- for (i = 0; i < n; i++) {
- cin >> a[i].first >> a[i].second;
- }
- for (i = 0; i < n; i++) {
- for (j = i + 1; j < n; j++) {
- gr[i].push_back({ j,getl(a[i].first, a[i].second, a[j].first, a[j].second) });
- gr[j].push_back({ i,getl(a[i].first, a[i].second, a[j].first, a[j].second) });
- }
- }
- vector <ld> d(n, inf);
- vector <bool> used(n, false);
- d[0] = 0;
- ld ans = 0;
- for (i = 0; i < n; i++) {
- ll v = -1;
- for (ll u = 0; u < n; u++) {
- if (!used[u] && (v == -1 || d[v] > d[u])) {
- v = u;
- }
- }
- used[v] = true;
- ans += d[v];
- for (auto [u, w] : gr[v]) {
- if (d[u] > w) {
- d[u] = w;
- }
- }
- }
- cout << fixed << setprecision(10)
- << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement