Cod sursa(job #1851795)

Utilizator DobosDobos Paul Dobos Data 20 ianuarie 2017 08:58:36
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <bits/stdc++.h>;
#define NMAX 2005

using namespace std;

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

struct point{
int x,y;
};

struct pointd{
    int x,y;
    double d;
    bool t;
};
pointd V[NMAX*NMAX];
point A[2*NMAX];
int G[NMAX];

void update(int nod,int n,int &nr){
    for(int i = 1; i < nod; i++){
        if(i > n || nod > n){
            V[++nr].x = i;
            V[nr].y = nod;
            V[nr].d = double(sqrt((A[i].x - A[nod].x)*(A[i].x - A[nod].x) + (A[i].y - A[nod].y)*(A[i].y - A[nod].y)));
        }
    }
}

struct cmp{
    bool operator()(const pointd &A,const pointd &B){
        return A.d < B.d;
    }
};

int grup(int nod){
    if(G[nod] == nod)
        return nod;
    return grup(G[nod]);
}
int grupeaza(int x,int y){
    G[grup(x)] = grup(y);
}

int main()
{
    ios :: sync_with_stdio(false);
    fin.tie(NULL);

    int n,m,nr = 0;

    fin >> n >> m;
    for(int i = 1; i <= n + m; i++){
        fin >> A[i].x >> A[i].y;
        update(i,n,nr);
    }

    sort(V + 1, V + n + m + 1,cmp());

    for(int i = 1; i <= n + m; i++)
        G[i] = i;

    int S = 0;

    for(int i = 1; i <= nr; i++){
        if(grup(V[i].x) != grup(V[i].y)){
            S += V[i].d;
            grupeaza(V[i].x,V[i].y);
        }

    }
    fout << S;

    return 0;
}