Pagini recente » Cod sursa (job #1716863) | Cod sursa (job #1216833) | Cod sursa (job #1922626) | Cod sursa (job #711815) | Cod sursa (job #657534)
Cod sursa(job #657534)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define NMAX 4000001
using namespace std;
ifstream f("retea2.in");
ofstream g("retea2.out");
struct poz {
int xp,yp;
};
float cost(poz a,poz b) {
float r;
r=(a.xp-b.xp)*(a.xp-b.xp)+(a.yp-b.yp)*(a.yp-b.yp);
r=(float)sqrt((float)r);
return r;
}
poz bl[3000],ct[3000];
int n,m,i,j;
int M;
float ANS=0;
int X[NMAX],Y[NMAX],GR[NMAX],I[NMAX];
float C[NMAX];
bool comp(int a,int b) {
return(C[a]<C[b]);
}
int rad(int x) {
int p,y;
for (p=x;p!=GR[p];p=GR[p]);
for (;x!=GR[x];) {
y=GR[x];
GR[x]=p;
x=y;
}
return p;
}
void unite(int x,int y) {
GR[y]=x;
}
int main () {
f >> n >> m;
for (i=1;i<=n;i++) f >> ct[i].xp >> ct[i].yp;
for (i=1;i<=m;i++) f >> bl[i].xp >> bl[i].yp;
for (i=1;i<=m;i++)
for (j=i+1;j<=m;j++) {
++M;
X[M]=i;Y[M]=j;C[M]=cost(bl[i],bl[j]);I[M]=M;
}
for (i=1;i<=n;i++)
for (j=1;j<=m;j++) {
X[M+j]=0;Y[M+j]=j;I[M+j]=M+j;
if (C[M+j]==0) C[M+j]=cost(bl[j],ct[i]);
else C[M+j]=min(C[M+j],cost(bl[j],ct[i]));
}
M=M+m;
sort(I+1,I+M+1,comp);
for (i=0;i<=m;i++) GR[i]=i;
for (i=1;i<=M;i++)
if(rad(X[I[i]])!=rad(Y[I[i]])) {
ANS+=C[I[i]];
unite(rad(X[I[i]]),rad(Y[I[i]]));
}
g << fixed;
g << setprecision(6) << ANS << '\n';
f.close();g.close();
return 0;
}