Solve day 10 part 2

I'm so fucking frustrated with this one. I was stuck for hours trying to
sort the points by angle not realizing that (int)(angle(a) - angle(b))
would be 0 for all angles with differences smaller than 1. I also wanted
to do the sort by atan2(-y, x) - π/2 intuitively to get "up" be zero,
but I never got that to work.

1 files changed, 40 insertions, 2 deletions

diff --git a/2019/day10.c b/2019/day10.c
index dbc2352..04743b4 100644
--- a/2019/day10.c
+++ b/2019/day10.c
@@ -1,3 +1,4 @@
+#include <math.h>
 #include <stdio.h>
 #include <stdlib.h>
 
@@ -25,6 +26,21 @@ static struct Point reduce(struct Point p) {
 	return p;
 }
 
+static double angle(struct Point p) {
+	double theta = atan2(p.x, -p.y);
+	return (theta < 0.0 ? theta + 2.0 * M_PI : theta);
+}
+
+static int compar(const void *_a, const void *_b) {
+	struct Point a = *(const struct Point *)_a;
+	struct Point b = *(const struct Point *)_b;
+	if (angle(a) == angle(b)) {
+		return copysign(1.0, hypot(a.x, a.y) - hypot(b.x, b.y));
+	} else {
+		return copysign(1.0, angle(a) - angle(b));
+	}
+}
+
 int main(void) {
 	struct Point ps[2048];
 	size_t len = 0;
@@ -38,7 +54,7 @@ int main(void) {
 		}
 	}
 
-	size_t max = 0;
+	size_t m, max = 0;
 	for (size_t i = 0; i < len; ++i) {
 		struct Point ds[2048];
 		size_t dlen = 0;
@@ -51,7 +67,29 @@ int main(void) {
 			}
 			if (d == dlen) ds[dlen++] = a;
 		}
-		if (dlen > max) max = dlen;
+		if (dlen > max) {
+			max = dlen;
+			m = i;
+		}
 	}
 	printf("%zu\n", max);
+
+	struct Point o = ps[m];
+	ps[m] = ps[--len];
+	for (size_t i = 0; i < len; ++i) {
+		ps[i] = sub(ps[i], o);
+	}
+	qsort(ps, len, sizeof(ps[0]), compar);
+	for (int n = 0;;) {
+		for (size_t i = 0; i < len; ++i) {
+			if (eq(ps[i], Point(0, 0))) continue;
+			if (++n == 200) {
+				printf("%d\n", 100 * (o.x + ps[i].x) + (o.y + ps[i].y));
+				return 0;
+			}
+			double theta = angle(ps[i]);
+			ps[i] = Point(0, 0);
+			while (i + 1 < len && angle(ps[i + 1]) == theta) i++;
+		}
+	}
 }