Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

Tree's a Crowd

152.c

/* 150 - Tree's a Crowd */
/* Thu Jun 10 18:14:47 CEST 2010 */

#include <stdio.h>

int ntrees;
int trees[5010][3];
int closest[5010];
int distances[10];

int
dist(int a, int b) {
	int d1, d2, d3;
	d1 = trees[a][0]-trees[b][0];
	d2 = trees[a][1]-trees[b][1];
	d3 = trees[a][2]-trees[b][2];

	return d1*d1 + d2*d2 + d3*d3;
}

int
main(void) {
	int i,j;
	int a,b,c;

	for (i=0; ; i++) {
		scanf("%d %d %d", &a, &b, &c);
		if (a!=0 || b!=0 || c!=0) {
			trees[ntrees][0] = a;
			trees[ntrees][1] = b;
			trees[ntrees][2] = c;
			ntrees++;
		} else {
			break;
		}
	}
	for (i=0; i<ntrees; i++) {
		closest[i] = 256*256*256;
	}
#if DEBUG
	printf("%d trees\n", ntrees);
#endif
	for (i=0; i<ntrees-1; i++) {
		for (j=i+1; j<ntrees; j++) {
			int d = dist(i,j);
			if (d < closest[i]) {
				closest[i] = d;
			}
			if (d < closest[j]) {
				closest[j] = d;
			}
#if DEBUG
			printf("dist(%d,%d) = %d\n", i,j,d);
#endif
		}
	}
	for (i=0; i<ntrees; i++) {
#if DEBUG
		printf("closest(%d) = %d\n", i, closest[i]);
#endif
		for (j=1; j<=10; j++) {
			if (closest[i] < j*j) {
				distances[j-1]++;
				break;
			}
		}
	}
	for (i=0; i<10; i++) {
		printf("%4d", distances[i]);
	}
	printf("\n");
	return 0;
}