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, positivearea 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 xcoordinate increases by $X_D$, and its ycoordinate by $Y_D$. These variables also have absolute values no greater than $10^9$, and at least one of them is guaranteed to be nonzero. 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$.
Input
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$
Output
For each scenario:
1 integer, the number of asteroids that will be destroyed by the missile
Example
Input:
1
4 4
4 17 4 2
5 16 15 18 12 9
16 13 13 11 14 10
20 9 20 7 18 7
22 5 23 11 27 6
Output:
2
Explanation of Sample:
The following grid shows the layout of the game, with your ship marked with an "S", and the missile's location at each frame marked with that frame's number:
As can be seen, the missile destroys the first asteroid during frame 1, and then the third asteroid during frame 4. It does not destroy the second asteroid, even though its line of fire goes through it, as it does not intersect the asteroid during any of the frames. It also doesn't destroy the last asteroid, as it stops travelling after frame 4.
hide comments
Ashwani Gautam:
20151220 12:38:27
anyone who can give AC solution in python or PyPy? 

:D:
20150328 13:10:05
Very nice problem, thanks. It could actually use a hard version, for example 1 <= N,F <= 10^5. 

Flago:
20140210 16:55:33
My PHP got TLE while same algorithm C++ run in 0.23s 

Romal Thoppilan:
20130619 14:36:51
Could ease the time limits a bit, if you're expecting an O(N*F) soln


Chandan Mittal:
20130607 01:51:33
finally AC :) Last edit: 20130621 08:27:07 

Zeeshan Ahmad:
20130604 08:28:44
Getting a WA :(


shadoww:
20130604 07:13:27
Wrong limits gave me 2WA's.


Pranay:
20130604 07:13:27
any tricky test cases? can't get why WA


mehmetin:
20130604 07:13:27
 Last edit: 20130523 17:22:22 
Added by:  SourSpinach 
Date:  20130517 
Time limit:  4s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem, used in the 2012 UofT ACM Tryouts 