Pagini recente » Cod sursa (job #1618159) | Cod sursa (job #1582528) | Cod sursa (job #1840482) | Statistici Diana-Valeria (dyana_valerya) | Cod sursa (job #2784898)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("desen.in");
ofstream fout("desen.out");
struct elem {
int x, y;
double dist;
};
const int nmax = 1000 + 5;
int n, m, t[nmax], c[nmax];
vector <pair <int, int> > v;
elem sume[500005], aux[nmax];
double calc(pair <int, int> x, pair <int, int> y) {
double ans = (y.first - x.first) * (y.first - x.first) + (y.second - x.second) * (y.second - x.second);
return sqrt(ans);
}
int cmp(elem a, elem b) {
return a.dist < b.dist;
}
int findd(int nr) {
if (nr != t[nr]) return t[nr] = findd(t[nr]);
return nr;
}
void unite(int k, int l) {
if (c[k] > c[l]) swap(k, l);
t[k] = l;
c[l] += c[k];
}
int main()
{
fin >> n;
for (int i = 0; i < n; ++i) {
int x, y;
fin >> x >> y;
v.push_back({x, y});
for (int k = 0; k < i; ++k) {
double s = calc(v[i], v[k]);
sume[++m] = {i + 1, k + 1, s};
}
sort(sume + 1, sume + 1 + m, cmp);
for (int j = 1; j <= i + 1; ++j) t[j] = j, c[j] = 1;
double cost = 0;
int m2 = 0;
for (int k = 1; k <= m; ++k) {
int nr1 = findd(sume[k].x);
int nr2 = findd(sume[k].y);
if (nr1 != nr2) {
unite(nr1, nr2);
cost += sume[k].dist;
aux[++m2] = {sume[k].x, sume[k].y, sume[k].dist};
}
}
m = m2;
for (int j = 1; j <= m; ++j) sume[j] = {aux[j].x, aux[j].y, aux[j].dist};
fout << setprecision(6) << fixed << cost << '\n';
}
return 0;
}