Given a rectangle on 2D plane ((0, 0), (a, b)) where 2 ≤ a, b ≤ 1000, two different points of me and another person (x1, y1) ≠ (x2, y2) such that x1, y1, x2, y2 are integers, 0 < x1, x2 < a, 0 < y1, y2 < b, and d — the range of our gun where 2 ≤ d ≤ 10000, find how many angles we can shoot at so that the bullet hits the other person and traveled at most a distance d.
When the bullet hits the wall it geometrically reflects against it, and if it hits the corner it bounces back.
Shooting another person means that the first person the bullet hits is the other person and not me, and the distance traveled by the bullet is at most d.
Sample: (a, b) = (3, 2), my position = (1, 1), other guy's position = (2, 1), d = 4
The answer is 7.
My solution right now is kind of reflect all the points over each of the walls, then do it over and over. Due to the constraints, it enough to reflect the points in each direction 5000 times. So in total, for directions it would give me somewhat around (2·5000)2·2 = 2·108 points. Afterward, I sort the points by the angle relative to (x1, y1) and just go in that order, making sure the distance between me and the point of interest is at most d and that there are no other points between us (that's what I sorted).
Now this is slow since there are many points, I just thought maybe there are some other solutions?
