#include #include #include struct coord4d { int x; int y; int z; int t; }; struct point { struct coord4d c; GPtrArray *near; }; struct point *parse_points(const char *fname, unsigned *len) { FILE *f = fopen(fname, "r"); if (!f) { perror(fname); return NULL; } GArray *array = g_array_new(FALSE, FALSE, sizeof(struct point)); struct point point; while (fscanf(f, "%d,%d,%d,%d\n", &point.c.x, &point.c.y, &point.c.z, &point.c.t) == 4) { point.near = g_ptr_array_new(); g_array_append_val(array, point); } *len = array->len; return (struct point *)g_array_free(array, FALSE); } void free_points(struct point *points, const unsigned len) { for (struct point *point = points; point < points + len; point++) { g_ptr_array_free(point->near, TRUE); } g_free(points); } GHashTable *find_const(GPtrArray *consts, struct point *point) { for (GHashTable **p = (GHashTable **)consts->pdata; p < (GHashTable **)consts->pdata + consts->len; p++) { if (g_hash_table_contains(*p, point)) return *p; } return NULL; } void merge_const(GPtrArray *consts, GHashTable *a, GHashTable *b) { if (a == b) return; GHashTableIter iter; gpointer key, value; g_hash_table_iter_init(&iter, b); while (g_hash_table_iter_next(&iter, &key, &value)) { g_hash_table_add(a, key); } g_ptr_array_remove_fast(consts, b); } int main() { unsigned points_len; struct point *points = parse_points("input", &points_len); if (!points) return 1; for (struct point *a = points; a < points + points_len; a++) { for (struct point *b = points; b < points + points_len; b++) { unsigned x = abs(a->c.x - b->c.x); unsigned y = abs(a->c.y - b->c.y); unsigned z = abs(a->c.z - b->c.z); unsigned t = abs(a->c.t - b->c.t); if (x + y + z + t <= 3) { g_ptr_array_add(a->near, b); } } } GPtrArray *consts = g_ptr_array_new(); g_ptr_array_set_free_func(consts, (void (*)(void *))g_hash_table_destroy); for (struct point *p = points; p < points + points_len; p++) { GHashTable *constel = find_const(consts, p); if (!constel) { constel = g_hash_table_new(NULL, NULL); g_hash_table_add(constel, p); g_ptr_array_add(consts, constel); } for (struct point **p2 = (struct point **)p->near->pdata; p2 < (struct point **)p->near->pdata + p->near->len; p2++) { GHashTable *constel2 = find_const(consts, *p2); if (constel2) merge_const(consts, constel, constel2); g_hash_table_add(constel, *p2); } } printf("%u\n", consts->len); g_ptr_array_free(consts, TRUE); free_points(points, points_len); return 0; }