Cod sursa(job #750074)

Utilizator Theorytheo .c Theory Data 20 mai 2012 15:04:20
Problema Arbori indexati binar Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.25 kb
#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;
}