Pagini recente » Cod sursa (job #1925868) | Cod sursa (job #1303119) | Cod sursa (job #2078897) | Cod sursa (job #2177639) | Cod sursa (job #3191936)
#include <bits/stdc++.h>
using namespace std;
using db = long double;
using pii = pair<int, int>;
using edge = tuple<db, int, int>;
const int NMAX = 1002;
int n;
pii v[NMAX];
vector<edge> edges;
ifstream fin("desen.in");
ofstream fout("desen.out");
struct DSU {
int n;
vector<int> t, sz;
DSU(int _n){
n = _n;
t.resize(n+1);
sz.resize(n+1);
for(int i = 1; i <= n; i++){
t[i] = i;
sz[i] = 1;
}
}
int root(int nod){
if(t[nod] == nod){
return nod;
}
return t[nod] = root(t[nod]);
}
void join(int x, int y){
x = root(x);
y = root(y);
if(sz[x] < sz[y]){
swap(x, y);
}
sz[x] += sz[y];
t[y] = x;
}
bool areJoined(int x, int y){
return root(x) == root(y);
}
};
db sqr(db x){
return (x*x);
}
db dist(pii a, pii b){
return sqrt(sqr(a.first - b.first) + sqr(a.second - b.second));
}
db apm(){
sort(edges.begin(), edges.end());
DSU ds(n);
db ans = 0;
vector<edge> nw;
for(int i = 0; i < edges.size(); i++){
auto [cost, x, y] = edges[i];
if(!ds.areJoined(x, y)){
ans += cost;
nw.push_back(edges[i]);
ds.join(x, y);
}
}
edges.clear();
edges = nw;
return ans;
}
int main()
{
fin >> n;
for(int i = 1; i <= n; i++){
fin >> v[i].first >> v[i].second;
}
for(int i = 1; i <= n; i++){
for(int j = i-1; j >= 1; j--){
edges.push_back({dist(v[j], v[i]), j, i});
}
fout << fixed << setprecision(6) << apm() << "\n";
}
return 0;
}