BZOJ1821_[JSOI]Group部落划分_KEY

/************************************************************** ???Problem: 1821 ???User: yekehe ???Language: C++ ???Result: Accepted ???Time:432 ms ???Memory:9136 kb****************************************************************/ #include <bits/stdc++.h>using namespace std;int a[1001],b[1001];int n,k,now,fa[1001];double p(double x1,double x2,double y1,double y2){ ???return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);}double w[1001];struct node{ ???int x,y; ???double c;}l[500001];inline int cmp(node x,node y){return x.c<y.c;}int getf(int x){return x==fa[x]?x:fa[x]=getf(fa[x]);}int main(){ ???scanf("%d%d",&n,&k); ???????for(int i=1;i<=n;i++) ???????????scanf("%d%d",&a[i],&b[i]); ???????for(int i=1;i<=n;i++) ???????????for(int j=i+1;j<=n;j++) ???????????????l[++now].x=i,l[now].y=j,l[now].c=p(a[i],a[j],b[i],b[j]); ???sort(l+1,l+now+1,cmp); ???????for(int i=1;i<=n;i++)fa[i]=i; ???int ans=0,i; ???????for(i=1;i<=now;i++){ ???????????int x=getf(l[i].x),y=getf(l[i].y),c=l[i].c; ???????????if(x!=y){ ???????????????fa[x]=y; ???????????????w[++ans]=c; ???????????????if(ans==n-1)break; ???????????} ???????} ???printf("%.2lf",sqrt(w[n-k+1])); ???return 0;}