#include #include #include #include typedef struct cell { double x, y, z, r; } cell; void solve(FILE *stream, int number_of_cells); void create_cost_matrix(int number_of_cells, cell cells[], double cost_matrix[]); #define cost(cell1, cell2) cost_matrix[(cell1) * number_of_cells + (cell2)] double spanning_tree_minimum_cost(int number_of_cells, double cost_matrix[]); double distance(cell *cell1, cell *cell2); int main() { #ifdef TARGET_RT_MAC_CFM FILE *stream = fopen("input", "r"); #else FILE *stream = stdin; #endif int number_of_cells; for (;;) { fscanf(stream, "%d", &number_of_cells); if (number_of_cells <= 0) break; solve(stream, number_of_cells); } return 0; } void solve(FILE *stream, int number_of_cells) { int index, index2; cell cells[100]; double *cost_matrix = malloc(sizeof(double) * number_of_cells * number_of_cells); if (!cost_matrix) { fprintf(stderr, "*** Out of memory!!\n"); exit(1); } memset(cells, 0, sizeof(cells)); for (index = 0; index < number_of_cells; index++) fscanf(stream, "%lf%lf%lf%lf", &cells[index].x, &cells[index].y, &cells[index].z, &cells[index].r); for (index = 0; index < number_of_cells; index++) { cost(index, index) = 0; for (index2 = index + 1; index2 < number_of_cells; index2++) { double dist = distance(&cells[index], &cells[index2]) - cells[index].r - cells[index2].r; if (dist < 0) dist = 0; cost(index, index2) = cost(index2, index) = dist; } } printf("%.3f\n", spanning_tree_minimum_cost(number_of_cells, cost_matrix)); free(cost_matrix); } double spanning_tree_minimum_cost(int number_of_cells, double cost_matrix[]) { double minimum_cost[100], total_cost = 0.0, infinity = 1e100; int nearest_cell[100], index, index2; for (index = 1; index < number_of_cells; index++) { minimum_cost[index] = cost(0, index); nearest_cell[index] = 0; } for (index = 1; index < number_of_cells; index++) { double min_cost = minimum_cost[1]; int min_index = 1; for (index2 = 2; index2 < number_of_cells; index2++) { if (minimum_cost[index2] < min_cost) { min_cost = minimum_cost[index2]; min_index = index2; } } total_cost += cost(min_index, nearest_cell[min_index]); minimum_cost[min_index] = infinity; for (index2 = 2; index2 < number_of_cells; index2++) { if (cost(min_index, index2) < minimum_cost[index2] && minimum_cost[index2] < infinity) { minimum_cost[index2] = cost(min_index, index2); nearest_cell[index2] = min_index; } } } return total_cost; } double distance(cell *cell1, cell *cell2) { double dx = cell1->x - cell2->x, dy = cell1->y - cell2->y, dz = cell1->z - cell2->z; return sqrt(dx * dx + dy * dy + dz * dz); }