[HOJ] 316 - Point group

#include<stdio.h>

#include<algorithm>

using namespace std;

struct P{

    int x,y,z;

}s[2005],arr[4000005];

int p[2005]={0};

int cmp(P a,P b){

    return a.z<b.z;

}

int find(int k){

    if(p[k]==k) return k;

    return p[k]=find(p[k]);

}

int main(){

    int n,m,i,j,add=0,x,y,z,tmp=0;

    scanf("%d%d",&n,&m);

    for(i=1;i<=n;i++)

        scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].z),p[i]=i;

    for(i=1;i<=n;i++)

        for(j=i+1;j<=n;j++)

            arr[add++]=(P){i,j,max(max(abs(s[i].x-s[j].x),abs(s[i].y-s[j].y)),abs(s[i].z-s[j].z))};

    sort(arr,arr+add,cmp);

    for(i=0;i<add && tmp<n-m;i++){

        x=find(arr[i].x);

        y=find(arr[i].y);

        if(x!=y) p[y]=x,tmp++;

    }

    for(i=0;i<add;i++){

        if(find(arr[i].x)!=find(arr[i].y)){

            printf("%d\n",arr[i].z);

            break;

        }

    }

}