monitoring station

approach

asteroids are a set of (x, y). from a given asteroid, every other one is reduced to a direction: the offset divided by its gcd. asteroids on the same line of sight share a direction, so the number of distinct directions is how many are visible. part 1 takes the asteroid that sees the most.

part 2 sorts those directions clockwise from straight up with atan2(dx, dy), then sweeps them, stepping outward along each direction until it hits an asteroid. it returns the coordinates of the 200th hit. hit asteroids aren't removed from the set, so this is only right when the first sweep already reaches 200, which holds when part 1's count is at least 200.

the trick

dividing an offset by its gcd gives a key that is the same for everything on that line of sight.

for (ox,oy) in asteroids:
    if (px,py)==(ox,oy):
        continue
    dx=ox-px
    dy=py-oy
    d=gcd(dx,dy)
    line=(dx//d,dy//d)
    if line not in detected:
        detected.add(line)