G - Arctic Network

G - Arctic Network

 

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAXN 510

using namespace std;

double an;

int fa[MAXN];

int t,n,m,tot,sum;

double x[MAXN],y[MAXN],ans[MAXN];

struct nond{

    int x,y;double z;

}v[MAXN*MAXN];

int cmp(nond a,nond b){

    return a.z<b.z;

}

int find(int x){

    if(fa[x]==x)    return x;

    else  return fa[x]=find(fa[x]);

}

int main(){

    scanf("%d",&t);

    while(t--){

        an=;sum=;tot=;

        scanf("%d%d",&n,&m);

        for(int i=;i<=m;i++)

            scanf("%lf%lf",&x[i],&y[i]);

        for(int i=;i<=m;i++)

            for(int j=i+;j<=m;j++){

                double tmp=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));

                v[++tot].x=i;v[tot].y=j;v[tot].z=tmp;

            }

        for(int i=;i<=m;i++)    fa[i]=i;

        sort(v+,v++tot,cmp);

        for(int i=;i<=tot;i++){

            int dx=find(v[i].x);

            int dy=find(v[i].y);

            if(dx==dy)    continue;

            fa[dy]=dx;

            ans[++sum]=v[i].z;

            if(sum==m-)    break;

        }

        for(int i=;i<=m-n;i++)

            an=max(an,ans[i]);

        printf("%.2lf\n",an);

    }

}