Problem D
Line Segment Intersection
Input
The first line of input contains an integer $n$ ($n \leq 10000$) giving the number of test cases. Then follow $n$ lines each containing 8 integers $x_1\ y_1\ x_2\ y_2\ x_3\ y_3\ x_4\ y_4$, indicating a line segment from $(x_1, y_1)$ to $(x_2, y_2)$, and a line segment from $(x_3, y_3)$ to $(x_4, y_4)$. Coordinates have absolute value at most 10000.
Output
For each test case, output the intersection between the two line segments in the following format:

If the intersection is empty (i.e. the segments do not intersect), output the word “none”.

If there is a unique intersection point $(X, Y)$, output the numbers $X$ and $Y$ separated by a single space.

If the intersection is itself a line segment between two points $(X1, Y1)$ and $(X2, Y2)$, output the numbers $X_1\ Y_1\ X_2\ Y_2$ separated by spaces, in that order. Pick the point with smallest $x$coordinate as the first point, or the point with smallest $y$coordinate if both have the same $x$coordinate.
Numbers should be given with 2 decimals of precision.
Sample Input 1  Sample Output 1 

5 10 0 10 0 0 10 0 10 10 0 10 0 5 0 5 0 1 1 1 1 1 1 2 1 1 1 1 1 2 1 2 1 1871 5789 216 517 189 518 3851 1895 
0.00 0.00 5.00 0.00 5.00 0.00 1.00 1.00 none 221.33 496.70 