Cod sursa(job #3192933)

Utilizator miu_anaMiu Ana Corina miu_ana Data 13 ianuarie 2024 15:58:30
Problema Iepuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2 kb
#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;
}