Arctic Network UVA - 10369 || MST

#include<bits/stdc++.h>
using namespace std;

typedef long long           ll;
typedef unsigned long long  ull;
typedef double              ld;//%Lf
#define ff                  first
#define ss                  second
#define pb                  push_back
#define mp                  make_pair
#define ppb                 pop_back
#define in                  insert
#define sz(a)               int((a).size())
#define vi                  vector<int>
#define vl                  vector<ll>
#define vvi                 vector<vector<int> >
#define pii                 pair<int,int>
#define piii                pair<int,pair<int,int> >
#define pll                 pair<ll,ll>
#define vii                 vector<pii>
#define vll                 vector<pll>
#define viii                vector<piii>
#define YES                 cout << "YES\n"
#define NO                  cout << "NO\n"

#define scl(n)              scanf("%lld",&n)
#define scll(x,y)           scanf("%lld %lld",&x,&y)
#define gtl(x)              getline(cin, (x))

#define f0(b)               for(int i=0;i<(b);i++)
#define f00(b)              for(int j=0;j<(b);j++)
#define f1(b)               for(int i=1;i<=(b);i++)
#define f11(b)              for(int j=1;j<=(b);j++)
#define f2(a,b)             for(int i=(a);i<=(b);i++)
#define f22(a,b)            for(int j=(a);j<=(b);j++)
#define RFOR(i,x,y)         for(int i=x;i>=y;i--)
#define all(v)              v.begin(),v.end()
#define rall(v)             v.rbegin(),v.rend()
#define unq(v)              sort(all(v)),(v).resize(unique(all(v))-v.begin())
#define present(c,x)        ((c).find(x) != (c).end())
#define cpresent(c,x)       (find(all(c),x) != (c).end())
#define min_ele(v)          (*min_element(all(v)))
#define max_ele(v)          (*max_element(all(v)))
#define cnt_ele(v, x)       (count(all(v), x))
#define sum_ele(v)          (accumulate(all(v),0))
#define reversed(s)         reverse(s.begin(), s.end())

#define testcase            ll t; cin>>t; while (t--)
#define vout(v)             for(int ind=0;ind<v.size();ind++){ cout<<v[ind]; if(ind<v.size()-1) cout<<' '; else cout<<endl;}
#define arrout(arr,i,x,y)   for(int i=x;i<=y;i++){ cout<<arr[i]; if(i<y) cout<<' '; else cout<<endl;}
#define PI                  acos(-1)
#define CLR(x, y)           memset(x, y, sizeof(x))
#define Precision(a)        cout << fixed << setprecision(a)
#define BITCH_FAST()        ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) //Don't use scanf/printf
#define MAXP                1000006
#define MOD                 1e9+7//10000007 // For big mod
#define EPS                 1e-7

template <typename T> T Sqr(T x) { T n = x * x ; return n ;}
template <typename T> T Pow(T B,T P){ if(P==0) return 1; if(P&1) return B*Pow(B,P-1);  else return Sqr(Pow(B,P/2));}
template <typename T> T Abs(T a) {if(a<0)return -a;else return a;}
template <typename T> T Gcd(T a,T b){if(a<0)return Gcd(-a,b);if(b<0)return Gcd(a,-b);return (b==0)?a:Gcd(b,a%b);} // better than __gcd
template <typename T> T Lcm(T a,T b) {if(a<0)return Lcm(-a,b);if(b<0)return Lcm(a,-b);return a*(b/Gcd(a,b));}
template <typename T> T power(T n, T p){ T res = 1;while(p > 0){if(p & 1)res *= n;n *= n;p >>= 1;}return res;}
template <typename T> T BigMod (T b,T p,T m){if (p == 0) return 1;if (p%2 == 0){T s = BigMod(b,p/2,m);return ((s%m)*(s%m))%m;}return ((b%m)*(BigMod(b,p-1,m)%m))%m;}
template <typename T> inline string ToBinary(T n) {string r ;while(n != 0) {r = ( n % 2 == 0 ? "0" : "1" ) + r ; n >>= 1;} return r ;}
long long BinaryToDecimal(string s) {int len = s.size();long long n = 0, p = 1;for (int i = len - 1; i >= 0; i-- , p *= 2) n += p * (s[i] - '0');return n;}
int Strtoint(string str){stringstream ss(str);int x = 0;ss >> x ;return x ;}
string Intostr(int x){stringstream ss; ss << x; string str = ss.str(); return str;}

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){
        cout << name << " : " << arg1 << endl;
        //use cerr if u want to display at the bottom
    }
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
    }
#else
#define trace(...)
#endif

/*----------------------Graph Moves----------------*/
int ROW[]={+1,-1,+0,+0};
int COL[]={+0,+0,+1,-1};

int X[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
int Y[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move

int KX[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
int KY[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move

int parent[1000000];
int find_parent(int v)
{
    if(parent[v]==v)
    {
        return v;
    }
    return parent[v]=find_parent(parent[v]);
}
double Dist(double x,double xx, double y, double yy)
{
    return sqrt((x-xx)*(x-xx) + (y-yy)*(y-yy));
}
int main()
{
    BITCH_FAST();
    #ifdef FLAME
        clock_t tStart = clock();
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    testcase
    {
        //edges.clear();
        int s, p;
        cin >> s >> p;
        ld a[p], b[p];
        vector<ld>vv;
        vector<pair<double,pair<int,int>>>edges;
        edges.clear();
        f0(p)
        {
            cin >> a[i] >> b[i];
            parent[i]=i;

        }
        f0(p)
        {
            for(int j=i+1; j<p; j++)
            {
                ld dis=Dist(a[i], a[j], b[i], b[j]);
                edges.pb({dis, {i, j}});
            }
        }
        sort(all(edges));
        int cnt=0;
        for(int i=0; i<sz(edges) && cnt<p-1; i++)
        {
            int x=edges[i].ss.ff;
            int k=edges[i].ss.ss;
            int u=find_parent(x);
            int v=find_parent(k);
            if(u!=v)
            {
                parent[u]=v;
                vv.pb(edges[i].ff);
                cnt++;
            }
        }
        sort(rall(vv));
        Precision(2) << vv[s-1] << endl;
        vv.clear();
    }
    #ifdef FLAME
        fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
    #endif
    return 0;
}