Pagini recente » Cod sursa (job #179723) | Cod sursa (job #2876600) | Cod sursa (job #888836) | Cod sursa (job #3189975) | Cod sursa (job #2946283)
#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 > ¢rale, 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 > ¢rale, 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;
}