Pagini recente » Cod sursa (job #1270118) | Cod sursa (job #3330075) | Cod sursa (job #2035594) | Cod sursa (job #1675305) | Cod sursa (job #1851795)
#include <bits/stdc++.h>;
#define NMAX 2005
using namespace std;
ifstream fin("retea2.in");
ofstream fout("retea2.out");
struct point{
int x,y;
};
struct pointd{
int x,y;
double d;
bool t;
};
pointd V[NMAX*NMAX];
point A[2*NMAX];
int G[NMAX];
void update(int nod,int n,int &nr){
for(int i = 1; i < nod; i++){
if(i > n || nod > n){
V[++nr].x = i;
V[nr].y = nod;
V[nr].d = double(sqrt((A[i].x - A[nod].x)*(A[i].x - A[nod].x) + (A[i].y - A[nod].y)*(A[i].y - A[nod].y)));
}
}
}
struct cmp{
bool operator()(const pointd &A,const pointd &B){
return A.d < B.d;
}
};
int grup(int nod){
if(G[nod] == nod)
return nod;
return grup(G[nod]);
}
int grupeaza(int x,int y){
G[grup(x)] = grup(y);
}
int main()
{
ios :: sync_with_stdio(false);
fin.tie(NULL);
int n,m,nr = 0;
fin >> n >> m;
for(int i = 1; i <= n + m; i++){
fin >> A[i].x >> A[i].y;
update(i,n,nr);
}
sort(V + 1, V + n + m + 1,cmp());
for(int i = 1; i <= n + m; i++)
G[i] = i;
int S = 0;
for(int i = 1; i <= nr; i++){
if(grup(V[i].x) != grup(V[i].y)){
S += V[i].d;
grupeaza(V[i].x,V[i].y);
}
}
fout << S;
return 0;
}