Cod sursa(job #2946283)

Utilizator Daniel7390Popescu Daniel Daniel7390 Data 24 noiembrie 2022 18:28:48
Problema Paduri de multimi disjuncte Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.03 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

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


class Centrala{

private:
    int x;

    int y;

public:
    Centrala (int x, int y) {

        this->x = x;
        this->y = y;
    }

    void setX (int x) {

        this->x = x;
    }

    void setY (int y) {

        this->y = y;
    }

    int getX () {

        return this->x;
    }


    int getY () {

        return this->y;
    }

};



class Bloc {

private:
    int x;

    int y;

public:
    Bloc (int x, int y) {

        this->x = x;
        this->y = y;
    }

    void setX (int x) {

        this->x = x;
    }

    void setY (int y) {

        this->y = y;
    }

    int getX () {

        return this->x;
    }


    int getY () {

        return this->y;
    }

};



template < typename first, typename second > double distanta (first a, second b) {

    return sqrt ((pow ((double) a.getX () - (double) b.getX (), 2) + pow (((double) a.getY () - (double) b.getY ()), 2)));
}


void citire (int n, int m, vector < Centrala > &centrale, vector < Bloc > &blocuri) {

    for (int i = 0; i < n; i++) {

        int q, w;
        fin >> q >> w;
        Centrala c (q, w);
        centrale.push_back (c);
    }

    for (int i = 0; i < m; i++) {

        int q, w;
        fin >> q >> w;
        Bloc b (q, w);
        blocuri.push_back (b);
    }

}



void centralaCeaMaiApropiata (int n, int m, vector < Centrala > &centrale, vector < Bloc > &blocuri, vector < double >&distante) {

    for (int i = 0; i < n; i++)

        for (int j = 0; j < m; j++) {

            distante[j] = min (distante[j], distanta (centrale[i], blocuri[j]));
        }

}

double Prim (int m, double minim, vector < bool > &vizitat, vector < Bloc > &blocuri, vector < double >&distante, int p, double cost) {

    for (int i = 0; i < m; i++) {

        minim = 99999999;
        for (int j = 0; j < m; j++){

            if (distante[j] < minim && vizitat[j]== false) {

                minim = distante[j];
                p = j;
            }
        }

        vizitat[p] = true;
        cost += minim;

        for (int k = 0; k < m; k++)
            if (vizitat[k] == false)
                distante[k] = min (distante[k], distanta (blocuri[p], blocuri[k]));

    }

    return cost;
}







int main () {

    vector < Centrala > centrale;
    vector < Bloc > blocuri;
    int n, m;
    fin >> n >> m;
    vector < double >distante(m, 99999999);
    vector < bool > vizitat(m, false);

    citire (n, m, centrale, blocuri);
    centralaCeaMaiApropiata (n, m, centrale, blocuri, distante);

    fin.close ();

    double minim = 99999999;
    int p = -1;
    double cost = 0;

    cost = Prim (m, minim, vizitat, blocuri, distante, p, cost);

    fout << fixed << setprecision (6) << cost;

    fout.close();

    return 0;

}