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?
Auto comment: topic has been updated by nhtrnm (previous revision, new revision, compare).
Auto comment: topic has been updated by nhtrnm (previous revision, new revision, compare).
May be this way?
That's what I was already doing. And that's too slow.
Rectangle has 4 edges, so we do 4 reflects and reflect-angle calculations. I don't know where there may be time limit.
You misunderstood it. The bullet can reflect multiple times against the wall.
But this 4 cases has minimal bullet path length, so one of this shots is minimal.
I need the number of all angles I can shoot at so that I still hit the target.
In such problems horizontal and vertical reflections are independent. Iterate over the number of horizontal reflections and find the maximum number of vertical ones so that the distance is in the given range. Complexity is O(d / max(a, b)).
We need to count number of different angles, but 2 horizontal plus 2 vertical reflections can result in same angle as 4 gorizontal plus 4 vertical reflections. For example, test a = b = 3, our position is (1;1), other guy's position is (2;2)
I think this is from foobar. I'm stuck in the same problem. I'm generating the same number of angles. But I preprocessed the input so that I don't iterate over the same slopes.
Still, at d=10000 and (a,b)= (1000,1000), my code runs at 1.7secs to find 53 distinct points.
What are the coordinates of shooter and target ?
Has anyone tried optimizing a naive solution?
Precompute the gcd of all pairs of numbers ≤ D in
.
Run the naive algorithm in
.
Represent the angles as coprime pairs (Δ x, Δ y) for each quadrant.
Use these pairs as indices for an array that stores the distance to the nearest hit with a given angle.
My implementation takes ~1.3s or 2.5s on Ideone (I have no Idea, why there's such a big fluctuation in runtime). If this is slightly too slow, one could precompute the answer for the worst-case input of a = 2, b = 3 for every value of D.