10034 - Freckles

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<fstream>
#include<cstring>
#include<cmath>
using namespace std;
#define Max 100
#define pb push_back
#define READ(f) freopen(f, "r", stdin)
#define Input struct pairs
#define G struct prims

Input
{
    pair<double,double>axis_pos;
    bool operator < (const Input& a) const{
        if(axis_pos.first!=a.axis_pos.first)
            return axis_pos.first>a.axis_pos.first;
        else
            return axis_pos.second>a.axis_pos.second;
    }
}p;

G
{
    int u,v;
    double cost;
        bool operator < (const G& a) const{
        return cost>a.cost;
    }
}g;

priority_queue<Input>q;
priority_queue<G>q2,q1,temp;
int flag[Max+1];

double calculate_cost(double x1,double x2,double y1,double y2)
{

    double cost;
    cost=sqrt(pow((x2-x1),2) + pow((y2-y1),2));
    return cost;
}

int main()
{
    //READ("10034.txt");
    int t,e,src;
    double x,y,sum=0;
    cin>>t;
    while(t)
    {
        memset(flag,0,sizeof(flag));
        sum=0;
        cin>>e;
        for(int i=0;i<e;i++)
        {
            cin>>p.axis_pos.first>>p.axis_pos.second;
            q.push(p);
        }
        while(!q.empty())
        {
            Input temp1,temp2;
            temp1=q.top();
            q.pop();
            if(q.empty()) break;
            else
            {
                temp2=q.top();
                g.cost=calculate_cost(temp1.axis_pos.first, temp2.axis_pos.first, temp1.axis_pos.second,temp2.axis_pos.second);
                g.u=(int)temp1.axis_pos.second;
                g.v=(int)temp2.axis_pos.second;
                q2.push(g);
            }
        }
        q1=q2;
    src=g.u;
    flag[src]=1;
    while(e)
    {
        while(!temp.empty())
        {
            G m;
            m=temp.top();
            q1.push(m);
            temp.pop();
        }
        q2=q1;
        while(!q2.empty())
        {
            G pop;
            pop=q2.top();
            if((flag[pop.u]) || (flag[pop.v]))
            {
                if((flag[pop.u]) && (flag[pop.v]))
                {
                    q2.pop();
                    continue;
                }
                else
                {
                    flag[pop.u]=flag[pop.v]=1;
                    sum+=pop.cost;
                    q2.pop();
                    q1.pop();
                    break;
                }

            }
            else
            {

                temp.push(pop);
                q2.pop();
                q1.pop();
            }
        }
        e--;
    }
    printf("%.2f\n",sum);
        t--;
        if(t) cout<<endl;
    }
    return 0;
}