8549: CGL_2_C : Cross Point
[Creator : ]
Description
For given two segments $s_1$ and $s_2$, print the coordinate of the cross point of them.
$s_1$ is formed by end points $p_0$ and $p_1$, and $s_2$ is formed by end points $p_2$ and $p_3$.
$s_1$ is formed by end points $p_0$ and $p_1$, and $s_2$ is formed by end points $p_2$ and $p_3$.
Input
The entire input looks like:
$x_{p_0}\ y_{p_0}\ x_{p_1}\ y_{p_1}\ x_{p_2}\ y_{p_2}\ x_{p_3}\ y_{p_3}$
q(the number of queries) 1st query 2nd query ... qth queryEach query consists of integer coordinates of end points of s1 and s2 in the following format:
$x_{p_0}\ y_{p_0}\ x_{p_1}\ y_{p_1}\ x_{p_2}\ y_{p_2}\ x_{p_3}\ y_{p_3}$
Output
For each query, print the coordinate of the cross point.
The output values should be in a decimal fraction with an error less than 0.00000001.
The output values should be in a decimal fraction with an error less than 0.00000001.
Constraints
$1 ≤ q ≤ 1000$
$-10000 ≤ x_{p_i}, y_{p_i} ≤ 10000$
$p_0≠p_1$ and $p_2≠p_3$.
$-10000 ≤ x_{p_i}, y_{p_i} ≤ 10000$
$p_0≠p_1$ and $p_2≠p_3$.
Sample 1 Input
3
0 0 2 0 1 1 1 -1
0 0 1 1 0 1 1 0
0 0 1 1 1 0 0 1
Sample 1 Output
1.0000000000 0.0000000000
0.5000000000 0.5000000000
0.5000000000 0.5000000000