SP14978 UOFTBC - Homemade Asteroids

Pew pew pew! Everyone loves Asteroids, the classic arcade game involving senselessly blasting asteroids into submission with a spaceship. In fact, you love it so much that you built your very own version to play at home! Unfortunately, it sucks. Your version of the game is played on a 2D plane, containing your ship (a dot at coordinates ( $ X_S $ , $ Y_S $ )) and $ N $ ( $ 1 \leq N \leq 1000 $ ) stationary, triangular, positive-area asteroids. The $ i $ th asteroid has vertices at coordinates ( $ X_{Ai} $ , $ Y_{Ai} $ ), ( $ X_{Bi} $ , $ Y_{Bi} $ ), and ( $ X_{Ci} $ , $ Y_{Ci} $ ). All coordinates in the input are integers with absolute values no greater than $ 10^9 $ , and no two objects occupy any of the same space (even on their edges or vertices). Your game only permits you to fire a single missile, which travels in a straight line, destroying every asteroid that it comes in contact with (even on its edges or vertices). However, it doesn't exactly move very smoothly - instead, it starts at your ship at frame 0, and after every frame, its x-coordinate increases by $ X_D $ , and its y-coordinate by $ Y_D $ . These variables also have absolute values no greater than $ 10^9 $ , and at least one of them is guaranteed to be non-zero. After frame $ F $ ( $ 1 \leq F \leq 1000 $ ), the missile simply disappears. There are $ T $ ( $ 1 \leq T \leq 20 $ ) scenarios as described above. For each, you'd like to predict how many different asteroids your missile will be able to take out before frame $ F+1 $ .

First line: 1 integer, $ T $ For each scenario: First line: 2 integers, $ N $ and $ F $ Second line: 4 integers, $ X_S $ , $ Y_S $ , $ X_D $ , and $ Y_D $ Next $ N $ lines: 6 integers, $ X_{Ai} $ , $ Y_{Ai} $ , $ X_{Bi} $ , $ Y_{Bi} $ , $ X_{Ci} $ , and $ Y_{Ci} $ , for $ i = 1..N $

For each scenario: 1 integer, the number of asteroids that will be destroyed by the missile