Pagini recente » Cod sursa (job #2712833) | Cod sursa (job #3214445) | Cod sursa (job #1242452) | Cod sursa (job #1291990) | Cod sursa (job #2942889)
//
//#include <iostream>
//#include <bits/stdc++.h>
//#define MAXX 4000
//
//using namespace std;
//
//ifstream f("retea2.in");
//ofstream g("retea2.out");
//
//int n, m;
//vector<pair<int, int>> blocuri, centrale;
//vector<double> distCentrala; // distanta fiecarui nod pana la cea mai apropiata centrala
//double distantaTotala; // distanta totala la final
//vector<bool> finalizat; // daca am decis pentru un nod care este distanta pe care o vom alege
//vector<double> distFinala; // distantele finale alese pentru a obtine APCM
//
//double dist(pair<int, int> p1, pair<int, int> p2) {
// return sqrt((pow(p1.first - p2.first, 2)) + pow((p1.second - p2.second), 2));
//}
//
//int main() {
//// int n, m;
// f >> n >> m;
//// blocuri.resize(m);
//// centrale.resize(n);
// distCentrala.resize(m + 1, MAXX);
// finalizat.resize(m + 1, false);
// distFinala.resize(m + 1, MAXX);
//
//// vector<pair<int, int>> blocuri, centrale;
//// vector<double> distCentrala(m+1, MAXX); // distanta pana la cea mai apropiata centrala
//// double distantaTotala = 0; // distanta totala la final
//// vector<bool> finalizat(m+1, false); // daca am ales distanta finala pentru un nod
//// vector<double> distFinala(m+1, MAXX); // distantele finale alese pentru a obtine un APM
//
// int x, y;
// for (int i = 0; i < n; i++) {
// f >> x >> y;
// centrale.push_back( make_pair(x,y) );
// }
// for (int i = 0; i < m; i++) {
// f >> x >> y;
// blocuri.push_back( make_pair(x,y) );
// }
//
// // calculam distanta de la fiecare bloc la cea mai apropiata centrala de el
// for (int i = 0; i < m; i++) {
// for (int j = 0; j < n; j++)
// distCentrala[i] = min(distCentrala[i], dist(blocuri[i], centrale[j]));
// distFinala[i] = distCentrala[i];
// }
//
//
// for ( int i = 0; i < m; i++) {
// double d = MAXX;
// int ultim = -1;
// // pentru fiecare nod care nu a fost finalizat il legam de cel mai apropiat nod deja finalizat
// // initial avem distantele bloc-centrala, asa ca vom cauta si distantele bloc-bloc
// for ( int j = 0; j < m; j++) {
// if (!finalizat[j]) {
// if (distFinala[j] < d) { // caut cea mai mica distFinala
// d = distFinala[j];
// ultim = j;
// }
// }
// }
// // actualizam distanta totala
// distantaTotala += d;
// // Calculam distantele de la ultimul nod ales la celelalte noduri
// // Modificam distFinala cu minimul dintre valorile existente si cele noi calculate astfel incat la urmatorul
// // pas vom alege cea mai mica distanta dintre un nod nevizitat la unul vizitat
// for ( int j = 0; j < m; j++)
// distFinala[j] = min(distFinala[j], dist(blocuri[j], blocuri[ultim]));
// finalizat[ultim] = true;
// }
// g << fixed << setprecision(6) << distantaTotala;
// return 0;
//}
//
//
//
/* Tratam centralele ca pe un singur nod in graf, calculam distanta de la fiecare bloc(nod) la cea mai aporpiata
* centrala. Folosind algoritmul lui Prim alegem cea mai mica distanta dintre nodul centralelor si nodurile blocurilor.
*/
#include <iostream>
#include <bits/stdc++.h>
#define INT_MAX 4000
using namespace std;
ifstream in("retea2.in");
ofstream out("retea2.out");
const int N = 2005;
const int M = 2005;
int n, m;
vector<pair<int, int>> centrale, blocuri;
vector<double> distantaCentrala; // distanta fiecarui nod pana la cea mai apropiata centrala
double finalDistance; // distanta totala la final
vector<bool> decided; // daca am decis pentru un nod care este distanta pe care o vom alege
vector<double> finalDistances; // distantele finale alese pentru a obtine APCM
double dist(pair<int, int> source, pair<int, int> dest) {
return sqrt((pow(source.first - dest.first, 2)) + pow((source.second - dest.second), 2));
}
void read() {
// alocare spatiu + citire
in >> n >> m;
distantaCentrala.resize(m + 1, INT_MAX);
decided.resize(m + 1, false);
finalDistances.resize(m + 1, INT_MAX);
int x, y;
for (int i = 0; i < n; i++) {
in >> x >> y;
centrale.push_back(make_pair(x, y));
}
for (int i = 0; i < m; i++) {
in >> x >> y;
blocuri.push_back(make_pair(x, y));
}
// calculam distanta de la fiecare bloc la cea mai apropiata centrala de el
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++)
distantaCentrala[i] = min(distantaCentrala[i], dist(blocuri[i], centrale[j]));
finalDistances[i] = distantaCentrala[i];
}
}
int main() {
read();
for (int i = 0; i < blocuri.size(); i++) {
double actDist = INT_MAX;
int lastChosen = -1;
// pentru fiecare nod care nu a fost ales il legam de cel mai apropiat nod deja ales
// initial se considera ales nodul centralelor pentru ca finalDistances retine distantele minime
// corespunzatoare centrala-bloc
{
for (int j = 0; j < blocuri.size(); j++) {
if (!decided[j]) {
if (finalDistances[j] < actDist) {
actDist = finalDistances[j];
lastChosen = j;
}
}
}
}
// actualizam distanta finala
finalDistance += actDist;
// Calculam distantele de la ultimul nod ales la celelalte noduri.
// Modificam finalDistances cu minimul dintre valorile existente si cele noi calculate astfel incat la urmatorul
// pas vom alege cea mai mica distanta dintre un nod nevizitat la unul vizitat.
for (int j = 0; j < blocuri.size(); j++)
finalDistances[j] = min(finalDistances[j], dist(blocuri[j], blocuri[lastChosen]));
decided[lastChosen] = true;
}
out << fixed << setprecision(6) << finalDistance;
return 0;
}