[Problem] Shooting in 2D plane

Правка en3, от nhtrnm, 2016-10-18 19:41:52

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?

Теги geometry

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский nhtrnm 2016-10-18 19:41:52 118
en2 Английский nhtrnm 2016-10-18 19:38:28 880 Tiny change: ' 2D plane `((0,0),(a,b))` where `2 ' - (published)
en1 Английский nhtrnm 2016-10-18 16:45:13 577 Initial revision (saved to drafts)