Pagini recente » Cod sursa (job #3254664) | Cod sursa (job #1510282) | Cod sursa (job #2580764) | Cod sursa (job #1883517) | Cod sursa (job #647467)
Cod sursa(job #647467)
#include <cstdio>
#include <cmath>
#define nmax 2010
#define eps 0.000001
int n, m, heap[nmax], poz[nmax], l, u[nmax];
long long cx[nmax], cy[nmax], x[nmax], y[nmax];
double d[nmax], sol;
int main()
{
freopen("retea2.in","r",stdin);
freopen("retea2.out","w",stdout);
scanf("%d %d", &n, &m);
int i, j, nod;
double c;
for (i=1; i<=n; i++) scanf("%d %d", &cx[i], &cy[i]);
for (i=1; i<=m; i++) scanf("%d %d", &x[i], &y[i]);
for (i=1; i<=m; i++) d[i]=-2;
for (i=1; i<=m; i++)
{
for (j=1; j<=n; j++)
{
c=(x[i]-cx[j])*(x[i]-cx[j])+(y[i]-cy[j])*(y[i]-cy[j]);
c=sqrt(c);
if (d[i]<-1 || c<d[i]) d[i]=c;
}
}
for (i=1; i<=m; i++)
{
c=-1;
for (j=1; j<=m; j++)
if (!u[j])
if (c==-1 || d[j]<c)
{
c=d[j];
nod=j;
}
u[nod]=1;
sol+=d[nod];
for (j=1; j<=m; j++)
if (!u[j])
{
c=(x[nod]-x[j])*(x[nod]-x[j])+(y[nod]-y[j])*(y[nod]-y[j]);
c=sqrt(c);
if (c+d[i]<d[j]) d[j]=c+d[i];
}
}
printf("%.6lf\n",sol);
}