Cod sursa(job #2944694)

Utilizator stefan431245Oprea Mihai-Stefan stefan431245 Data 22 noiembrie 2022 20:56:35
Problema Paduri de multimi disjuncte Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.06 kb
#include <fstream>
#include <cmath>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

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

int N, M, x, y;
vector<vector<int>> centrale;
vector<vector<int>> blocuri;
vector<double> distante( 2000, 1000000 );

//functie pentru calcularea distantei
double func_distanta( vector<int> a, vector<int> b ) {
    return sqrt( pow( a[0] - b[0], 2 ) + pow( a[1] - b[1], 2 ) );
}

/*
    Idee algoritmului este ca mai intai sa gasim cea mai apropiata centrala de fiecare bloc
iar in timp ce parcurgem graful vedem daca unul din blocurile conectate la o centrala
este mai apropiat
    Complexitate O(n^2)
*/

int main() {
    fin >> N >> M;

    for( int i = 0; i < N; i++ ) {
        fin >> x >> y;
        centrale.push_back( {x, y} );
    }
    for( int i = 0; i < M; i++ ) {
        fin >> x >> y;
        blocuri.push_back( {x, y} );
    }

    //calculam cea mai apropiata centrala pentru fiecare bloc
    for( int i = 0; i < N; i++ )
        for( int j = 0; j < M; j++ )
            distante[j] = min( func_distanta( centrale[i], blocuri[j] ), distante[j] );

    vector<bool> visited( M + 1, false );
    double sum = 0;

    for( int i = 0; i < M; i++ ) {
        int U;
        double minimun = 1000000;

        //gasim blocul cel mai apropiat de o centrala sau cel mai apropiat de un bloc legat la o centrala
        for( int j = 0; j < M; j++ ) {
            if( visited[j] == false && distante[j] < minimun ) {
                U = j;
                minimun = distante[j];
            }
        }

        visited[U] = true;
        sum += minimun;

        //recalculam distantele minime sa vedem daca blocurile sunt mai apropiate de un bloc legat de o centrala
        //decat de o centrala
        for( int j = 0; j < M; j++ ) {
            if( visited[j] == false ) {
                distante[j] = min( func_distanta( blocuri[U], blocuri[j] ), distante[j] );
            }
        }
    }

    fout << fixed << setprecision( 7 ) << sum;

    return 0;
}