Cod sursa(job #3344045)

Utilizator Dragos__1_1Dragos Antohi Dragos__1_1 Data 1 martie 2026 11:03:12
Problema Radiatie Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("desen.in");
ofstream g("desen.out");
int t,n,m,i,j,a,b,c,d;
vector<pair<int,int>>adj;
double ans,dist;
int fat[2003],sz[2003];
void make_set(int node){
    fat[node]=node;
    sz[node]=1;
}
int get_fat(int node){
    if (fat[node]==node)return node;
    return fat[node]=get_fat(fat[node]);
}
void unite_set(int a,int b){
    a=get_fat(a);
    b=get_fat(b);
    if (sz[a]>sz[b])swap(a,b);
    if (a!=b){
        fat[a]=b;
        sz[b]+=a;
    }
}
priority_queue<tuple<double,int,int>,
        vector<tuple<double,int,int>>,greater<tuple<double,int,int>>>GL;
int main()
{   f>>t;
    while(t--){
        f>>a>>b;
        adj.push_back({a,b});
        priority_queue<tuple<double,int,int>,
        vector<tuple<double,int,int>>,greater<tuple<double,int,int>>>PQ;
        for (i=0;i<adj.size()-1;i++){
            tie(c,d)=adj[i];
            double dist=sqrt((a-c)*(a-c)+(b-d)*(b-d));
            GL.push({dist,i,adj.size()-1});
        }
        PQ=GL;
        ans=0;
        while(GL.size())GL.pop();
        for (i=0;i<adj.size();i++){
            make_set(i);
        }
        while(!PQ.empty()){
            tie(dist,a,b)=PQ.top();
            PQ.pop();
            if (get_fat(a)!=get_fat(b)){
                unite_set(a,b);
                ans+=dist;
                GL.push({dist,a,b});
            }
        }
        g<<fixed<<setprecision(7)<<ans<<'\n';
    }
    return 0;
}