Given a rectangle on 2D plane $((0,0),(a,b))$ where $2 \leq a,b \leq 1000$, two different points of me and another person $(x_1, y_1) \neq (x_2, y_2)$ such that $x_1,y_1,x_2,y_2$ are integers, $0 < x_1,x_2 < a$, $0 < y_1,y_2 < b$, and $d$ — the range of our gun where $2 \leq d \leq 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 \cdot 5000)^2 \cdot 2 = 2 \cdot 10^8$ points. Afterward, I sort the points by the angle relative to $(x_1, y_1)$ 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?
↵
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 \cdot 5000)^2 \cdot 2 = 2 \cdot 10^8$ points. Afterward, I sort the points by the angle relative to $(x_1, y_1)$ 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?
