- #include < algorithm > #include < iostream > #include < cstring > #include < cstdio > #include < queue > #include < cmath > #include < map > using namespace std;#define maxn 1100000 int n,
- m,
- k,
- x[maxn],
- cnt,
- y[maxn],
- tot;
- int num,
- w[2333][2333],
- fa[maxn];
- double ans[maxn];
- struct Edge {
- int l,
- r;
- double w;
- }
- edge[maxn];
- char ch;
- inline void read(int & now) {
- ch = getchar();
- now = 0;
- while (ch > ‘9‘ || ch < ‘0‘) ch = getchar();
- while (ch >= ‘0‘ && ch <= ‘9‘) now = now * 10 + ch - ‘0‘,
- ch = getchar();
- }
- int find(int x) {
- return fa[x] == x ? x: fa[x] = find(fa[x]);
- }
- void add_edge(int l, int r) {
- edge[++num].l = l;
- edge[num].r = r;
- edge[num].w = sqrt(pow(x[l] - x[r], 2) + pow(y[l] - y[r], 2));
- }
- bool cmp(Edge a, Edge b) {
- return a.w < b.w;
- }
- bool cmp2(double a, double b) {
- return a > b;
- }
- int main() {
- // freopen("people.in","r",stdin);
- // freopen("people.out","w",stdout);
- read(n);
- read(k);
- for (int i = 1; i <= n; i++) read(x[i]),
- read(y[i]);
- for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) add_edge(i, j);
- for (int i = 1; i <= n; i++) fa[i] = i;
- sort(edge + 1, edge + num + 1, cmp);
- for (int i = 1; i <= num; i++) {
- int fx = find(edge[i].l),
- fy = find(edge[i].r);
- if (fx != fy) {
- fa[fx] = fy;
- tot++;
- ans[++cnt] = edge[i].w;
- if (tot == n - 1) break;
- }
- }
- sort(ans + 1, ans + n + 1, cmp2);
- printf("%.2lf", ans[k - 1]);
- return 0;
- }
- /*
- 5 3
- 5 9
- 7 5
- 2 5
- 3 5
- 6 9
- */
来源: http://www.bubuko.com/infodetail-2294453.html