UltramanMK3 PROG1115

#include<stdio.h>
#include<queue>
using namespace std;

struct pos{
    int I,J;
};

struct edge{
    int u;
    int v;
    int w;
    bool operator < (const edge& rhs)const
    {
        return w > rhs.w;
    }
};

int dist(pos x,pos y){
    return ((x.I - y.I)*(x.I - y.I))+((x.J - y.J)*(x.J - y.J));
}

int parent[1010];

int find(int x){
    if(x == parent[x]){
        return x;
    }
    return parent[x] = find(parent[x]);
}

void unions(int x,int y){
    int rx = find(x);
    int ry = find(y);
    parent[rx] = ry;
}

int main()
{
    for(int i = 0 ; i < 1010 ; i++)parent[i] = i;
    int n,k;
    scanf("%d %d",&n,&k);
    priority_queue<edge> pq;
    pos house[n];
    for(int i = 0 ; i < n ; i++){
        scanf("%d %d",&house[i].I,&house[i].J);
        for(int j = i - 1 ; j >= 0 ; j --){
            pq.push({i,j,dist(house[i],house[j])});
        }
    }
/*  if(n == k){
        printf("0");
        return 0;
    }*/
//  vector<int> dist;
    int ans = 0;
    int cnt = 0;
    while(!pq.empty() && cnt < n - k){
        int u = pq.top().u;
        int v = pq.top().v;
        int w = pq.top().w;
    //  printf("%d\n",pq.top().w);
        pq.pop();
        if(find(u) != find(v)){
            cnt++;
            unions(u,v);
        //  dist.push_back(w);
            ans = w;
        }
    }
//  printf("%d",dist[dist.size() - k]);
    printf("%d",ans);
    return 0;
}