Cod sursa(job #2784898)

Utilizator MihneaCadar101Cadar Mihnea MihneaCadar101 Data 17 octombrie 2021 17:46:19
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#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;
}