PROG-1115: อุลตร้าแมน (Ultraman)

#include <bits/stdc++.h>
using namespace std;
using pi = pair<int,int>;
using pii = pair<int,pi>;
using pfi = pair<double,pi>;
int parent[15001];
pi ar[15001];
double distance(pi a,pi b ){
    int d1,d2;
    d1=a.first-b.first;
    d2=a.second-b.second;
    return sqrt(d1*d1+d2*d2);
}
int root(int u){
    if( parent[u] == u ) return u;
    return parent[u] = root(parent[u]) ;
}
int main(){

    int n,k;
    scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++){
        int x,y;
        scanf("%d%d",&ar[i].first,&ar[i].second);
        parent[i]=i;
    }

    vector <pfi> pq;

    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            pq.push_back({distance(ar[i],ar[j]),{i,j}});
        }
    }

    sort( pq.begin() , pq.end() );

    int node=n-k;
    double dis=0.0;
    for(int i=0;i<pq.size();i++){

        int u,v;
        double d;
        d=pq[i].first;
        u=pq[i].second.first;
        v=pq[i].second.second;

        u=root(u);
        v=root(v);
        if(u==v) continue;
        parent[u]=v;
        dis=d;
        node--;
        if(node==0) break;

    }

    printf("%.0f",dis*dis);

    return 0;
}
// หาเส้นที่ยาวที่สุดจากการเชื่มต่อที่สั้นที่สุดโดยต้องมีจำนวนกลุ่มตามโจทย์