#include #include #include #include struct point { int x; int y; int area_size; }; struct point *strict_nearest(struct point list[], int count, int x, int y) { int shortest = INT_MAX; struct point *p, *nearest = 0; for (p = list; p < &list[count]; ++p) { int distance = abs(x - p->x) + abs(y - p->y); if (distance == shortest) nearest = 0; if (distance < shortest) { shortest = distance; nearest = p; } } return nearest; } #define IO_ERROR 3 #define TOO_MANY_POINTS 2 #define BAD_INPUT_FORMAT 1 int main(int argc, char *argv[]) { #define MAX_POINTS 100 static struct point points[MAX_POINTS]; int npoints = 0, left = INT_MAX, right = INT_MIN, top = INT_MAX, bottom = INT_MIN; /* Grab all the input points. While doing that, also * find all four extremes of the input coordinates. */ { FILE *input; int error = IO_ERROR; if (input = fopen(argc > 1? argv[1]: "input.txt", "r")) { #define MAX_INPUT_WIDTH 20 static char buf[MAX_INPUT_WIDTH]; error = 0; while (fgets(buf, MAX_INPUT_WIDTH, input)) { error = TOO_MANY_POINTS; if (npoints < MAX_POINTS) { struct point *p = &points[npoints]; error = BAD_INPUT_FORMAT; if ( buf[strlen(buf) - 1] == '\n' && sscanf(buf, "%d, %d", &p->x, &p->y) == 2 ) { error = 0; p->area_size = 0; if (p->x < left) left = p->x; if (p->x > right) right = p->x; if (p->y < top) top = p->y; if (p->y > bottom) bottom = p->y; ++npoints; } } if (error) break; } fclose(input); } if (error) return error; } /* Scan the edges of the bounding box and set the area_size on * all points for which an edge is nearest neighbor to -1. */ { int x; struct point *p; for (x = left; x <= right; ++x) { p = strict_nearest(points, npoints, x, top); if (p) p->area_size = -1; p = strict_nearest(points, npoints, x, bottom); if (p) p->area_size = -1; } } { int y; struct point *p; for (y = top + 1; y < bottom; ++y) { p = strict_nearest(points, npoints, left, y); if (p) p->area_size = -1; p = strict_nearest(points, npoints, right, y); if (p) p->area_size = -1; } } /* Scan the interior of the bounding box and accumulate area_size * for all points that don't already have it set to -1. */ { int x, y; struct point *p; for (y = top + 1; y < bottom; ++y) { for (x = left + 1; x < right; ++x) { p = strict_nearest(points, npoints, x, y); if (p && p->area_size >= 0) p->area_size++; } } } /* Walk the list of points and find the biggest area_size. */ { int biggest = -1; struct point *p; for (p = points; p < &points[npoints]; ++p) { if (p->area_size > biggest) biggest = p->area_size; } printf("%d\n", biggest); } return 0; }