uppgb.c (2015B)
1 #include "common.h" 2 3 typedef struct { 4 int x; 5 int y; 6 int d; 7 } boll; 8 9 #define LMT 4000000 10 11 static inline int d(boll a, boll b) { return abs(a.x - b.x) + abs(a.y - b.y); } 12 13 static inline int inaball(int x, int y, boll *bs, size_t n) { 14 size_t i; 15 for (i = 0; i < n; i++) 16 if (abs(bs[i].x - x) + abs(bs[i].y - y) <= bs[i].d) 17 return 1; 18 return 0; 19 } 20 21 int main(int argc, char **argv) { 22 char **lines; 23 size_t nlines = readlines(&lines, "input"); 24 25 boll bs[nlines]; 26 int x1, y1; 27 size_t i, j; 28 for (i = 0; i < nlines; i++) { 29 sscanf(lines[i], "Sensor at x=%d, y=%d: closest beacon is at x=%d, y=%d", 30 &bs[i].x, &bs[i].y, &x1, &y1); 31 bs[i].d = abs(bs[i].x - x1) + abs(bs[i].y - y1); 32 } 33 34 size_t ndownlines = 0; 35 int downline[4 * nlines]; 36 size_t nuplines = 0; 37 int upline[4 * nlines]; 38 39 for (i = 0; i < nlines; i++) { 40 for (j = i + 1; j < nlines; j++) { 41 if (d(bs[i], bs[j]) == bs[i].d + bs[j].d + 2) { 42 if (abs(bs[i].x - bs[j].x + bs[i].y - bs[j].y) == 43 bs[i].d + bs[j].d + 2) { 44 if (bs[i].x - bs[j].x + bs[i].y - bs[j].y == bs[i].d + bs[j].d + 2) { 45 downline[ndownlines] = bs[i].x + bs[i].y - bs[i].d - 1; 46 } else { 47 downline[ndownlines] = bs[i].x + bs[i].y - bs[i].d + 1; 48 } 49 ndownlines++; 50 } else { 51 if (bs[j].x - bs[i].x + bs[i].y - bs[j].y == bs[i].d + bs[j].d + 2) { 52 upline[nuplines] = -bs[i].y + bs[i].x + bs[i].d + 1; 53 } else { 54 upline[nuplines] = -bs[i].y + bs[i].x - bs[i].d - 1; 55 } 56 nuplines++; 57 } 58 } 59 } 60 } 61 62 for (i = 0; i < ndownlines; i++) { 63 for (j = 0; j < nuplines; j++) { 64 int x, y; 65 x = (downline[i] + upline[j]) / 2; 66 y = (downline[i] - upline[j]) / 2; 67 if (x >= 0 && y >= 0 && x <= LMT && y <= LMT && 68 !inaball(x, y, bs, nlines)) { 69 printf("%llu\n", ((uint64_t)x) * ((uint64_t)LMT) + ((uint64_t)y)); 70 return 0; 71 } 72 } 73 } 74 75 return 0; 76 }