Pagini recente » Cod sursa (job #3238568) | Cod sursa (job #3255877) | Cod sursa (job #2972196) | Cod sursa (job #1946078) | Cod sursa (job #2946631)
#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;
}