Pagini recente » Cod sursa (job #1607110) | Cod sursa (job #547170) | Cod sursa (job #2724432) | Cod sursa (job #552236) | Cod sursa (job #750074)
Cod sursa(job #750074)
#include<fstream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<iomanip>
#define nmax 1002
using namespace std;
ifstream fin("desen.in");
ofstream fout("desen.out");
struct Punct {int a,b; };
struct Muchie {int c1, c2; double cost;};
Muchie M[nmax * nmax /2];
int i, j ,n ,Nr, k ;
Punct P[nmax];
int IND[nmax * nmax /2];
int T[nmax *nmax /2];
int gr[nmax * nmax /2];
inline bool cmp(int k,int h)
{
if( M[k].cost < M[h].cost)
return true;
return false;
}
double lungime(Punct h, Punct k)
{
return sqrt((h.a- k.a) * (h.a - k.a) + (h.b- k.b) * (h.b - k.b));
}
int find(int x)
{
int R ;
for(R = x; R != T[R] ; R = T[R]);
for( ; x != T[x]; )
{
int y = T[x] ;
T[x] = R;
x = y;
}
return R;
}
void unite(int x,int y)
{
if(gr[x] >gr[y])
T[y] = x;
else
T[x] = y;
if(gr[x]==gr[y])
gr[x]++;
}
double det_apm(int Nrmuc)
{
int i, j;
int Muc = 0;
double costt = 0;
int R1, R2;
// int Nrmuc = 0;
for(i = 0 ; i <= Nr; i++, T[i] = i,gr[i] = 1);
for(i = 1; Muc < Nrmuc - 1; ++i)
{
// if(viz[IND[i]]== 0)
R1 = find(M[IND[i]].c1);
R2 = find(M[IND[i]].c2);
if(R1 != R2)
{
unite(R1, R2);
Muc++;
costt += M[IND[i]].cost;
}
}
return costt;
// for(i = 1; i <= Nr; i++, T[i] = 1);
}
void read()
{
fin >> n;
double lung = 0 ;
int i;
for(i = 1; i <= n ;i++)
{
fin >> P[i].a >> P[i].b;
//Nr = 0;
for(j = 1; j < i ;j++)
{
lung = lungime(P[i],P[j]);
M[++Nr].cost = lung;
M[Nr].c1 = i;
M[Nr].c2 = j;
IND[Nr] = Nr;
// M[++Nr].cost = lung;
// M[Nr].c1 = j;
// M[Nr].c2 = i;
// IND[Nr] = Nr;
}
sort(IND + 1, IND + 1 + Nr, cmp);
// for(j = 1; j <= Nr; ++j)
// fout << M[IND[j]].cost <<" " ;
// fout <<'\n';
fout << fixed;
fout <<setprecision(6) << det_apm(i) <<'\n';
}
}
int main()
{
read();
fin.close();
return 0;
}