8548: CGL_2_B : Intersection
[Creator : ]
Description
For given two segments $s_1$ and $s_2$, print "1" if they are intersect, "0" otherwise.
$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 "1" or "0".
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 3 0 1 1 2 -1
0 0 3 0 3 1 3 -1
0 0 3 0 3 -2 5 0
Sample 1 Output
1
1
0
