/* prim 题意：给定一些点，一些卫星，一个卫星能连接两个点，点和点之间通信有一定的距离限制。 问能使得所有的点联通的最小距离。 */ #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long int64; //typedef __int64 int64; typedef pair PII; #define MP(a,b) make_pair((a),(b)) const int maxn = 505; const int inf = 0x7fffffff; const double pi=acos(-1.0); const double eps = 1e-8; struct Node{ double x,y; }a[ maxn ]; int vis[ maxn ]; double dis[ maxn ]; double mat[ maxn ][ maxn ]; double dist( Node a,Node b ){ return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) ); } void init( int n ){ for( int i=1;i<=n;i++ ){ for( int j=1;j<=n;j++ ){ mat[i][j] = dist( a[i],a[j] ); } } return ; } void prim( int n ){ for( int i=1;i<=n;i++ ){ vis[ i ] = 0; dis[ i ] = mat[1][i]; } vis[ 1 ] = 1; for( int i=1;i<=n;i++ ){ int M = inf; int id = -1; for( int j=1;j<=n;j++ ){ if( vis[ j ]==0&&M>dis[j] ){ M = dis[ j ]; id = j; } } if( id==-1 ) return ; vis[ id ] = 1; for( int j=1;j<=n;j++ ){ if( vis[j]==0&&dis[j]>mat[ id ][ j ] ){ dis[ j ] = mat[ id ][ j ]; } } } return ; } int main(){ int T; scanf("%d",&T); while( T-- ){ int s,n; scanf("%d%d",&s,&n); for( int i=1;i<=n;i++ ) scanf("%lf%lf",&a[i].x,&a[i].y); init( n ); prim( n ); sort( dis+1,dis+1+n ); //for( int i=1;i<=n;i++ ) // printf("%lf ",dis[ i ]); //puts(""); printf("%.2lf\n",dis[ n-s+1 ]); } return 0; }