Seletiva IOI 2013

caminhos.cpp

// Ivan Carvalho
// Caminhos - Seletiva IOI - OBI 2013
#include <bits/stdc++.h>
#define MP make_pair
#define MAXN 5100
#define PESO first
#define U second.first
#define V second.second
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,ii> iii;
ll x[MAXN],y[MAXN],z[MAXN];
int n,c,resposta,pai[MAXN],peso[MAXN];
double minimo = 1e9;
vector<iii> original;
int find(int x){
	if (x==pai[x]) return x;
	return pai[x]=find(pai[x]);
}
inline void join(int x, int y){
	if (peso[x]<peso[y]) pai[x] = y;
	else if (peso[x]>peso[y]) pai[y] = x;
	else {pai[x] = y; peso[y]++;}
}
double Kruskal(){
	for(int i=1;i<=n+1;i++) {
		pai[i] = i;
		peso[i] = 1;
	}
	double custo = 0.0;
	int contador = 0, ini = 0;
	priority_queue<iii, vector<iii> , greater<iii> > adicional;
	for(int i=1;i<=n;i++) adicional.push(MP((x[i]-x[n+1])*(x[i]-x[n+1])+(y[i]-y[n+1])*(y[i]-y[n+1])+(z[i]-z[n+1])*(z[i]-z[n+1]),MP(i,n+1)));
	while(contador != n){
		iii davez;
		if (adicional.top() < original[ini]) {
			davez = adicional.top();
			adicional.pop();
		}
		else davez = original[ini++];
		int u = find(davez.U), v = find(davez.V);
		ll peso = davez.PESO;
		if (u  != v){
			join(u,v);
			custo += sqrt(peso);
			contador++;
		}
	}
	return custo;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> c;
	for(int i=1;i<=n;i++) cin >> x[i] >> y[i] >> z[i];
	for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) original.push_back(MP((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]),MP(i,j)));
	sort(original.begin(),original.end());
	for(int i=1;i<=c;i++){
		cin >> x[n+1] >> y[n+1] >> z[n+1];
		double davez = Kruskal();
		//printf("Davez %lf\n",davez);
		if (davez < minimo){
			resposta = i;
			minimo = davez;
		}
	}
	cout << resposta << endl;
	return 0;
}