Cod sursa(job #1164155)

Utilizator mvcl3Marian Iacob mvcl3 Data 1 aprilie 2014 21:36:32
Problema Energii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.94 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <queue>

#define in "retea2.in"
#define out "retea2.out"
#define Max_Size 2009
#define oo 100000000.00

typedef std :: pair < double, double >  POINT;
typedef std :: pair < std :: pair < int, int> , double > MUCHIE;

std :: ifstream f(in);
std :: ofstream g(out);

std :: vector <MUCHIE > Graph;
int P[Max_Size], Rank[Max_Size];

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

class Retea {
    public  :
        double Get_Distance(POINT, POINT);
        double Get_Min_Cost(std :: vector < POINT >, std :: vector < double >);
        std :: vector < double > Proc(std :: vector < POINT >, std :: vector < POINT>);
};

double Retea :: Get_Distance(POINT A, POINT B)  {
    double  D = (A.first - B.first) * (A.first - B.first) + (A.second - B.second) * (A.second - B.second);
    D = sqrt(D);

    return D;
}

std :: vector < double > Retea :: Proc(std :: vector < POINT > Bloc, std :: vector < POINT > Centrala)  {
    std :: vector < double > D(Bloc.size());
    for(int i = 0; i < D.size(); ++i)   D[i] = Get_Distance(Bloc[i], Centrala[0]);

    for(int i = 0; i < Bloc.size(); ++i)
        for(int j = 1; j < Centrala.size(); ++j)
            if(D[i] > Get_Distance(Centrala[j], Bloc[i]))   D[i] = Get_Distance(Centrala[j], Bloc[i]);

    return D;
}

double Retea :: Get_Min_Cost(std :: vector < POINT > Bloc, std :: vector < double > D)   {
    double ans = 0;
    bool Viz[Bloc.size()][Bloc.size()];
    for(int i = 0; i < Bloc.size(); ++i)
        for(int j = 0; j < Bloc.size(); ++j)    Viz[i][j] = 0;

    std :: queue < int > Q;

    Q.push(0);  ans = D[0];
    while(!Q.empty())   {
        int nod = Q.front(), tnod;    Q.pop();
        double cost = oo;   bool ok = 0;
        for(int j = 0; j < Bloc.size(); ++j)
            if(nod != j && !Viz[nod][j]) {
                if(D[nod] + Get_Distance(Bloc[nod], Bloc[j]) < D[j])  {
                    if(D[nod] + Get_Distance(Bloc[nod], Bloc[j]) < cost) ok = 1, cost = D[nod] + Get_Distance(Bloc[nod], Bloc[j]), tnod = j;
                }
                else
                if(D[nod] + Get_Distance(Bloc[nod], Bloc[j]) > D[j])
                    if(D[j] < cost)    cost = D[j], tnod = j, ok = 1;
            }
        if(!Viz[nod][tnod] && !Viz[tnod][nod] && ok)  {
            Viz[nod][tnod] = Viz[tnod][nod] = 1;
            ans += cost;
            Q.push(tnod);
        }
    }

    return ans;
}

int main()  {
    Retea obj;
    int N, M;

    f >> N >> M;
    std :: vector < POINT > C(N), B(M), D(M + N);
    std :: vector < double > Distance(M);
    for(int i = 0; i < N; ++i)  f >> C[i].first >> C[i].second, D[i] = C[i];
    for(int j = 0; j < M; ++j)  f >> B[j].first >> B[j].second, D[j + N] = B[j];

    Distance = obj.Proc(B, C);

    g << std :: fixed;
    g << std :: setprecision(6) << obj.Get_Min_Cost(B, Distance) << '\n';

    g.close();
    return 0;
}