10034 - Freckles

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#define MAX 10000
using namespace std;
int par[MAX];
struct node
{
    double u,v;
    double cost;
} arr2[MAX];
int khoj_rep(int r)
{
    if(par[r]==r)
    {
        return r;
    }
    else
    {
        return par[r]=khoj_rep(par[r]);
    }
}
bool cmp(node lhs,node rhs)
{
    return lhs.cost<rhs.cost;
}
int main()
{
    int test,n,i,j,k,u,v,counter,tag=0;
    double arr[MAX],arr1[MAX],a,b,c,sum;
    scanf("%d",&test);
    while(test--)
    {
        if(tag!=0)
        {
            printf("\n");
        }
        tag=1;
        scanf("%d",&n);
        for(i=1; i<=n; i++)
        {
            scanf("%lf%lf",&arr[i],&arr1[i]);
        }
        k=0;
        for(j=1; j<=n; j++)
        {
            par[j]=j;
        }
        k=0;
        for(i=1; i<=n; i++)
        {
            for(j=i+1; j<=n; j++)
            {
                a=pow((arr[i]-arr[j]),2);
                b=pow((arr1[i]-arr1[j]),2);
                c=sqrt(a+b);
                arr2[k].u=i;
                arr2[k].v=j;
                arr2[k].cost=c;
                k++;
            }
        }
        sort(arr2,arr2+k,cmp);
        counter=0;
        sum=0.0;
        for(i=0; i<k; i++)
        {
            u=khoj_rep(arr2[i].u);
            v=khoj_rep(arr2[i].v);
            if(u!=v)
            {
                par[u]=v;
                counter++;
                sum+=arr2[i].cost;
                if(counter==n-1)
                {
                    break;
                }
            }
        }
        printf("%.2lf\n",sum);
        memset(arr2,0.0,sizeof(arr2));
    }
    return 0;
}