Tired of all the geometry problems in programming contests, you decided to run away from programming contests and get into game development - without realizing that there were more geometry problems waiting for you! You thought up of a nice two player 2-D arcade game which works as follows - the first player throws a triangular metal piece in a particular direction. The second player then throws another triangular metal piece with the aim of hitting the first player's piece. You're very confident that the game will be a worldwide hit - except that you don't know how to decide whether the two pieces will collide.
You've decided to get rid of your mental block and solve this problem at any cost. At the instant that the second player throws his piece, you store the position and velocity of both the pieces, and you refer to this time as 0. Your game does not allow the pieces to already be in collision at this time. You now want to compute the time at which the two pieces will collide.
Note:
Collision is defined as when the two triangle will end up bumping into each other, meaning that in some particular time they have a STRICTLY POSITIVELY intersecting area. That is, merely touching each other but not bumping into each other is not recognized as a collision.
The first line contains T, the number of test cases. Each test case contains two lines. The first line
describes the first player's piece and the second line describes the second player's piece. Each description
contains 8 space separated integers - x1, y1, x2, y2, x3, y3, vx, vy. (xi, yi) denotes the position of one of
the ith vertex of the piece. vx and vy denote respectively the x and y components of the velocity of the
piece.
For each test case, output a single line containing the earliest time at which the two pieces collide. The answer must be output as a floating number with 4 digits after the floating point. If the pieces will never collide, output a single line saying "NO COLLISION" (quotes for clarity).
2 0 0 1 0 0 -1 1 0 2 0 3 0 2 -1 0 0 0 0 1 0 0 -1 5 0 2 0 3 0 2 -1 5 0
1.0000 NO COLLISION
Migrated from old NTUJ.
ACM-ICPC Asia-Amritapuri Site 2009
| No. | Testdata Range | Score |
|---|