ACM-ICPC Asia-Amritapuri Site 2009
A: Geometry Problem
Time Limit :: 4 Seconds
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.
Input Format:
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.
Constraints:
1 <= T <= 100
-10000000 <= x1, y1, x2, y2, x3, y3, vx, vy <= +10000000
Output Format:
For each test case, output a single line containing the earliest time at which the two pieces collide. The answer must have a relative/absolute accuracy of 1e-9. If the pieces will never collide, output a single line saying "NO COLLISION" (quotes for clarity).
Sample Input:
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
Sample Output:
1.000000000
NO COLLISION
Problemsetter: Ajay Somani
Special thanks to: Prasanna Sankaranarayanan, Harsha Suryanarayana, Adrian Kuegel