#include #include #include #include struct point { int x; int y; }; int total_distance(struct point list[], int count, int x, int y) { int sum = 0; struct point *p; for (p = list; p < &list[count]; ++p) { sum += abs(x - p->x) + abs(y - p->y); } // printf("%d %d %d\n", x, y, sum); return sum; } #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; int left = INT_MAX, right = INT_MIN, top = INT_MAX, bottom = INT_MIN; int limit = 10000, region_size = 0; /* 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; 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; } /* Allow distance limit to be modified on the command line */ if (argc > 2) { sscanf(argv[2], "%d", &limit); // printf("limit: %d\n", limit); } /* Scan the interior of the bounding box and accumulate a count * of locations less than the required maximum distance from all * the input points. */ { int x, y; for (y = top + 1; y < bottom; ++y) { for (x = left + 1; x < right; ++x) { region_size += (total_distance(points, npoints, x, y) < limit); } } // printf("region: %d\n", region_size); } /* Scan the edges of the bounding box one at a time, expanding the * box until no point on an edge falls within the required region; * this guarantees that the region is entirely contained within the * box and all possible candidate points have been considered. */ for (;;) { int edge_size, x; edge_size = 0; for (x = left; x <= right; ++x) { edge_size += (total_distance(points, npoints, x, top) < limit); } // printf("top edge: %d\n", edge_size); if (edge_size) { region_size += edge_size; --top; } else break; } for (;;) { int edge_size, x; edge_size = 0; for (x = left; x <= right; ++x) { edge_size += (total_distance(points, npoints, x, bottom) < limit); } // printf("bottom edge: %d\n", edge_size); if (edge_size) { region_size += edge_size; ++bottom; } else break; } for (;;) { int edge_size, y; edge_size = 0; for (y = top; y <= bottom; ++y) { edge_size += (total_distance(points, npoints, left, y) < limit); } // printf("left edge: %d\n", edge_size); if (edge_size) { region_size += edge_size; --left; } else break; } for (;;) { int edge_size, y; edge_size = 0; for (y = top; y <= bottom; ++y) { edge_size += (total_distance(points, npoints, right, y) < limit); } // printf("right edge: %d\n", edge_size); if (edge_size) { region_size += edge_size; ++right; } else break; } printf("%d\n", region_size); return 0; }