common.c (1576B)
1 #include "common.h" 2 3 void parse(int *coords, char **lines, size_t nlines) { 4 size_t i; 5 for (i = 0; i < nlines; i++) { 6 sscanf(lines[i], "Sensor at x=%d, y=%d: closest beacon is at x=%d, y=%d", 7 &coords[4 * i], &coords[4 * i + 1], &coords[4 * i + 2], 8 &coords[4 * i + 3]); 9 } 10 } 11 12 static inline int min(const int x, const int y) { return x < y ? x : y; } 13 14 static inline int max(const int x, const int y) { return x < y ? y : x; } 15 16 static inline int overlap(const iv *x, const iv *y) { 17 return (x->a <= y->b && y->b <= x->b) || (y->a <= x->b && x->b <= y->b); 18 } 19 20 void insert_interval(lh *head, iv *t) { 21 assert(t->a <= t->b); 22 23 iv *k; 24 LIST_FOREACH(k, head, entries) { 25 if (overlap(k, t)) { 26 t->a = min(k->a, t->a); 27 t->b = max(k->b, t->b); 28 LIST_REMOVE(k, entries); 29 insert_interval(head, t); 30 return; 31 } 32 } 33 LIST_INSERT_HEAD(head, t, entries); 34 } 35 36 lh *compintervals(int *coords, size_t n, int yl) { 37 int x0, y0, x1, y1, d; 38 39 lh *ret = malloc(sizeof(*ret)); 40 LIST_INIT(ret); 41 42 iv *t; 43 44 size_t i; 45 for (i = 0; i < n; i++) { 46 x0 = coords[4 * i]; 47 y0 = coords[4 * i + 1]; 48 x1 = coords[4 * i + 2]; 49 y1 = coords[4 * i + 3]; 50 d = abs(x0 - x1) + abs(y0 - y1); 51 if (abs(y0 - yl) <= d) { 52 t = malloc(sizeof(*t)); 53 t->a = x0 - d + abs(y0 - yl); 54 t->b = x0 + d - abs(y0 - yl); 55 insert_interval(ret, t); 56 } 57 } 58 59 return ret; 60 } 61 62 void clear_lh(lh *head) { 63 iv *t; 64 while (!LIST_EMPTY(head)) { 65 t = LIST_FIRST(head); 66 LIST_REMOVE(t, entries); 67 free(t); 68 } 69 free(head); 70 }