Pagini recente » Cod sursa (job #2585662) | Cod sursa (job #2781236) | Cod sursa (job #2888224) | Cod sursa (job #846126) | Cod sursa (job #2944694)
#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;
}