Cod sursa(job #2946631)

Utilizator alex_bb8Banilean Alexandru-Ioan alex_bb8 Data 25 noiembrie 2022 00:38:57
Problema Paduri de multimi disjuncte Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("retea2.in");
ofstream g("retea2.out");


int n, m;
double dist[2001], sol;
vector<bool> visited(2001, false);
vector<pair<int,int>> centrale;
vector<pair<int,int>> blocuri;

double distance(pair<int,int>& a, pair<int,int>& b){
	int x = a.first - b.first;
	int y = a.second - b.second;
	return sqrtl(1ll * x * x + 1ll * y * y);
}

int main(){

	f >> n >> m;

	for(int i = 0; i < n; ++i){
		int x, y;
		f >> x >> y;
		centrale.push_back({x, y});
	}

	for(int i = 0; i < m; ++i){
		int x, y;
		f >> x >> y;
		blocuri.push_back({x, y});
		dist[i] = DBL_MAX;
	}

	for(int i = 0; i < m; ++i)
		for(int j = 0; j < n; ++j)
			dist[i] = min(dist[i], distance(centrale[j], blocuri[i]));

	for(int i = 0; i < m; ++i){
		double dst = DBL_MAX;
		int node = -1;

		for(int j = 0; j < m; ++j)
			if(!visited[j] && dist[j] < dst){
				dst = dist[j];
				node = j;
			}

		visited[node] = true;
		sol += dst;

		for(int j = 0; j < m; ++j)
			if(!visited[j])
				dist[j] = min(dist[j], distance(blocuri[node], blocuri[j]));
	}

	g << fixed << setprecision(6) << sol << '\n';

	f.close();
	g.close();

	return 0;
}