day09.c (4081B)
1 #include <stdio.h> 2 #include <inttypes.h> 3 #include <stdlib.h> 4 #include <stdbool.h> 5 #include "cputime.h" 6 7 #define MAX(a,b) (((a)>(b))?(a):(b)) 8 #define MIN(a,b) (((a)<(b))?(a):(b)) 9 10 #define MAX_POINTS 500 11 12 typedef union { 13 struct { int x, y; }; 14 int n[2]; 15 } Point; 16 17 typedef struct { 18 Point p1; 19 Point p2; 20 } Line; 21 22 static int64_t square(Point p1, Point p2) { 23 return (llabs(p1.x-p2.x)+1) * (llabs(p1.y-p2.y)+1); 24 } 25 26 static int btoi(int bufl, int buf[bufl]) { 27 int num = 0; 28 for (int i=0;i<bufl;++i) num = num*10+buf[i]; 29 return num; 30 } 31 32 static int cmp_int64(const void *vi1, const void *vi2) { 33 int64_t r = *(const int64_t *)vi2 - *(const int64_t *)vi1; 34 if (r>0) return 1; 35 if (r<0) return -1; 36 return 0; 37 } 38 39 static bool square_has_points(int points_l, Point points[points_l], Point p1, Point p2) { 40 int minx = MIN(p1.x, p2.x); 41 int miny = MIN(p1.y, p2.y); 42 int maxx = MAX(p1.x, p2.x); 43 int maxy = MAX(p1.y, p2.y); 44 for (int i=0;i<points_l;++i) { 45 Point p = points[i]; 46 if ((p.x==p1.x&&p.y==p1.y)||(p.x==p2.x&&p.y==p2.y)) continue; 47 if (p.x<maxx&&p.x>minx&&p.y<maxy&&p.y>miny) return true; 48 } 49 return false; 50 } 51 52 // essentially check for ovelaps in lines 53 static bool square_is_valid(int lines_l, Line lines[lines_l], Point p1, Point p2) { 54 Point p3 = (Point){ .x=p1.x, .y=p2.y }; 55 Point p4 = (Point){ .x=p2.x, .y=p1.y }; 56 int x1 = MIN(p1.x, p2.x); 57 int x2 = MAX(p1.x, p2.x); 58 int y1 = MIN(p1.y, p2.y); 59 int y2 = MAX(p1.y, p2.y); 60 for (int i=0;i<lines_l;++i) { 61 Line l = lines[i]; 62 if (l.p1.x==p1.x&&l.p1.y==p1.y&&l.p2.x==p2.x&&l.p2.y==p2.y) continue; // skip self 63 int lx1 = MIN(l.p1.x, l.p2.x); 64 int lx2 = MAX(l.p1.x, l.p2.x); 65 int ly1 = MIN(l.p1.y, l.p2.y); 66 int ly2 = MAX(l.p1.y, l.p2.y); 67 if ((p3.x==lx1&&p3.y==ly1)|| 68 (p3.x==lx2&&p3.y==ly2)|| 69 (p4.x==lx1&&p4.y==ly1)|| 70 (p4.x==lx2&&p4.y==ly2)|| 71 (p1.x==lx1&&p1.y==ly1)|| 72 (p1.x==lx2&&p1.y==ly2)|| 73 (p2.x==lx1&&p2.y==ly1)|| 74 (p2.x==lx2&&p2.y==ly2) 75 ) continue; // skip checking lines that connected directly to those points 76 if (lx1<=x1&&lx2>=x2&&ly1>=y1&&ly2<=y2) return false; 77 if (ly1<=y1&&ly2>=y2&&lx1>=x1&&lx2<=x2) return false; 78 } 79 return true; 80 } 81 82 int main(void) { 83 int64_t part1 = 0; 84 int64_t part2 = 0; 85 Point *points = calloc(MAX_POINTS, sizeof(Point)); 86 int points_l = 0; 87 int *n = points[0].n; 88 int buf[16] = {0}; 89 int bufl = 0; 90 for (int c=getchar();c!=EOF;c=getchar()) { 91 if (c>='0'&&c<='9') buf[bufl++] = c-'0'; 92 else if (c==','||c=='\n') { 93 *n = btoi(bufl, buf); 94 bufl = 0; 95 n++; 96 if (c=='\n') n = points[++points_l].n; 97 } 98 if (points_l>MAX_POINTS) { 99 printf("Too many input points, max: %d\n", MAX_POINTS); 100 return 1; 101 } 102 } 103 int lines_max = points_l; 104 Line lines[lines_max]; 105 int lines_l = 0; 106 for (int i=0;i<points_l-1;++i) { 107 lines[lines_l++] = (Line){ points[i], points[i+1] }; 108 } 109 lines[lines_l++] = (Line){ points[0], points[points_l-1] }; 110 int squares_max = (points_l*points_l-points_l)/2; 111 int64_t squares[squares_max]; 112 int squares_l = 0; 113 int64_t squares2[squares_max]; 114 int squares2_l = 0; 115 for (int i=0;i<points_l;++i) { 116 for (int j=i;j<points_l;++j) { 117 if (i==j) continue; 118 int64_t sq = square(points[i], points[j]); 119 squares[squares_l++] = sq; 120 if (!square_has_points(points_l, points, points[i], points[j]) && 121 square_is_valid(lines_l, lines, points[i], points[j])) { 122 squares2[squares2_l++] = sq; 123 } 124 } 125 } 126 qsort(squares, squares_l, sizeof(squares[0]), cmp_int64); 127 qsort(squares2, squares2_l, sizeof(squares2[0]), cmp_int64); 128 part1 = squares[0]; 129 part2 = squares2[0]; 130 free(points); 131 printf("p1: %"PRIi64"\np2: %"PRIi64"\n", part1, part2); 132 return 0; 133 }