Pagini recente » Cod sursa (job #1295224) | Cod sursa (job #2592917) | Cod sursa (job #543513) | Cod sursa (job #2765284) | Cod sursa (job #3192932)
#include <fstream>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("retea2.in");
ofstream fout("retea2.out");
// Structura pentru a reprezenta un punct cu coordonate x, y
struct Punct
{
long long x, y;
};
Punct centrale[2001], blocuri[2001];
long long distMin[2001], vizitat[2001];
// Functie pentru calcularea distantei euclidiene patratice intre doua puncte
long long dist(Punct a, Punct b)
{
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
int main()
{
int n, m;
fin >> n >> m;
// Citirea coordonatelor centralelor si blocurilor
for(int i = 1; i <= n; i++)
{
fin >> centrale[i].x >> centrale[i].y;
}
for(int i = 1; i <= m; i++)
{
fin >> blocuri[i].x >> blocuri[i].y;
distMin[i] = 1e18; // Initializare cu o valoare foarte mare
}
// Determinarea distantei minime de la fiecare bloc la o centrala
for(int i = 1; i <= m; i++)
{
long long minDist = 1e18;
for(int j = 1; j <= n; j++)
{
minDist = min(minDist, dist(blocuri[i], centrale[j]));
}
distMin[i] = minDist;
}
// Implementarea algoritmului pentru conectarea blocurilor
for(int i = 1; i <= m; i++)
{
long long minDist = 1e18;
int pozitie = 0;
for(int j = 1; j <= m; j++)
{
if(!vizitat[j] && distMin[j] < minDist)
{
minDist = distMin[j];
pozitie = j;
}
}
vizitat[pozitie] = 1;
for(int j = 1; j <= m; j++)
{
if(!vizitat[j] && distMin[j] > dist(blocuri[pozitie], blocuri[j]))
{
distMin[j] = dist(blocuri[pozitie], blocuri[j]);
}
}
}
// Calcularea costului total
double solutie = 0;
for(int i = 1; i <= m; i++)
{
solutie += sqrt(distMin[i]);
}
fout << fixed << setprecision(7) << solutie;
return 0;
}