Cod sursa(job #2569449)

Utilizator serafimalex2001Serafim Alex serafimalex2001 Data 4 martie 2020 12:11:41
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.06 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;

ifstream fin("desen.in");
ofstream fout("desen.out");

const int INF = 1<<25;

struct punct{
    int x,y;
}p[1009];

int m[1005],sz[1005];

struct segment{
    int x,y;
    double d;
}a[100008];

vector<segment> A;

double dist(punct A, punct B)
{
    return sqrt( (A.x-B.x)*(A.x-B.x) + (A.y - B.y) * (A.y-B.y) );
}

int N;

bool comp(segment A, segment B)
{
    return A.d < B.d;
}

int Find(int val)
{
    int root = val;
    while(root!= m[root])
        root = m[root];
    while(m[val] != root)
    {
        int aux = m[val];
        m[val] = root;
        val = aux;
    }
    return root;
}

void Union(int X, int Y)
{
    int rootx = Find(X);
    int rooty = Find(Y);
    if(sz[rootx] > sz[rooty])
    {
        sz[rootx] += sz[rooty];
        m[rooty] = rootx;
    }
    else
    {
        sz[rooty] += sz[rootx];
        m[rootx] = rooty;
    }
}

void Do()
{
    int i,j;
    int w,z;
    double c;
    double total = 0;
    vector<segment>Aux;
    sort(A.begin(), A.end(), comp);
    for(i = 0; i<A.size(); ++i)
    {
        w = A[i].x;
        z = A[i].y;
        c = A[i].d;
        if(Find(w) != Find(z))
        {
            total += c;
            Union(w,z);
            Aux.push_back(A[i]);
        }
    }
    A.erase(A.begin(), A.end());
    for( i = 0; i<Aux.size(); ++i)
        A.push_back(Aux[i]);
    fout<<fixed<<setprecision(6)<<total<<"\n";

}

void Read()
{
    int i,j;
    double c;
    segment aux;
    fin>>N;
    for(i = 1; i<=N; ++i)
    {
        fin>>p[i].x>>p[i].y;
        for(j = 1; j <=i; ++j)
       {
            m[j] = j;
            sz[j] = 1;
        }
        for(j = 1; j < i; ++j)
        {
            c = dist(p[i], p[j]);
            aux.x = i;
            aux.y = j;
            aux.d = c;
            A.push_back(aux);
        }
        Do();
    }
}

int main()
{
    Read();
    return 0;
}