diff options
| -rw-r--r-- | 2019/day10.c | 42 |
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++; + } + } } |