1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
| #include<bits/stdc++.h> #define N 1010 #define sqr(a) ((a)*(a)) #define fsb(a,b,c) for(register int a=b;a<=(c);a++) #define fbs(a,b,c) for(register int a=b;a>=(c);a--) using namespace std; struct node{ int x,y; }a[N],b[N*N]; int n,m,cnt=0,fa[N]; inline double getdis(int i,int j){ return sqrt(sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y)); } inline int cmp(node a,node b){ return getdis(a.x,a.y)<getdis(b.x,b.y); } inline int getf(int x){ return x==fa[x]?x:fa[x]=getf(fa[x]); } template<typename qw>inline void rll(qw &x){ x=0;qw f=1;char c=getchar(); while(!isdigit(c))f=c=='-'?-1:f,c=getchar(); while(isdigit(c))x=x*10+c-'0',c=getchar(); } int main(){ rll(n);rll(m); fsb(i,1,n){ rll(a[i].x);rll(a[i].y); fsb(j,1,i-1)b[++cnt]=(node){j,i}; } sort(b+1,b+1+cnt,cmp); fsb(i,1,n)fa[i]=i; fsb(i,1,cnt){ int fax=getf(b[i].x),fay=getf(b[i].y); if(fax==fay)continue; if(n==m){ printf("%0.2lf",getdis(b[i].x,b[i].y)); return 0; } fa[fay]=fax; n--; } return 0; }
|