Pagini recente » Cod sursa (job #2846642) | Cod sursa (job #2108432) | Cod sursa (job #3286464) | Cod sursa (job #1301203) | Cod sursa (job #534833)
Cod sursa(job #534833)
#include<algorithm>
#include<vector>
#include<math.h>
using namespace std;
#define N_MAX 3003
#define fs first
#define sc second
typedef pair <float,float> p;
typedef pair <int,int> pp;
p xy[N_MAX];
int nrMuchii;
int n,i,j;
float rez;
float dist(p a,p b)
{
return sqrtf( (a.fs-b.fs)*(a.fs-b.fs)+(a.sc-b.sc)*(a.sc-b.sc) );
}
float cost[N_MAX];
bool inArb[N_MAX];
int main()
{
freopen("cablaj.in","r",stdin);
freopen("cablaj.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%f%f",&xy[i].fs,&xy[i].sc);
inArb[1]=1;
for(i=2;i<=n;i++)
{
cost[i]=dist( xy[1],xy[i] );
}
for(i=1;i<n;i++)
{
int nd=1;
float Min=(1<<20);
for(j=1;j<=n;j++)
{
if(inArb[j])
continue;
if(cost[j]<Min)
{
Min=cost[j];
nd=j;
}
}
//rez+=cost[nd];
inArb[nd]=1;
for(j=1;j<=n;j++)
{
if(j==nd)
continue;
if(inArb[j])
continue;
if(dist( xy[nd],xy[j] )<cost[j])
{
cost[j]=dist( xy[nd],xy[j] );
}
}
}
for(i=2;i<=n;i++)
rez+=cost[i];
printf("%f\n",rez);
return 0;
}