UVa 11966 - Galactic Bonding

// UVa 11966 - Galactic Bonding

#include <stdio.h>
#include <string.h>

double point[1000][2];
bool seen[1000];
int n;
double dd;

/**
 * Computes the square of the distance
 */
double dist2(int i, int j) {
	double dx = point[i][0] - point[j][0];
	double dy = point[i][1] - point[j][1];
	return dx * dx + dy * dy;
}

void visit(int node) {
	seen[node] = true;
	for (int i = 0; i < n; i++)
		if (!seen[i] && dist2(i, node) <= dd)
			visit(i);
}

int countConstellations() {
	int constellations = 0;
	for (int i = 0; i < n; i++)
		if (!seen[i]) {
			constellations++;
			visit(i);
		}
	return constellations;
}

int main() {

	int cases;
	scanf("%d", &cases);
	for (int cas = 1; cas <= cases; cas++) {
		double d;
		scanf("%d %lf", &n, &d);
		dd = d * d;
		for (int i = 0; i < n; i++)
			scanf("%lf %lf", &point[i][0], &point[i][1]);

		memset(seen, false, sizeof(seen));
		printf("Case %d: %d\n", cas, countConstellations());
	}

	return 0;
}