- Time limit: 1.00 s
- Memory limit: 512 MB
Your task is to determine if the line segments intersect, i.e., they have at least one common point.
Input
The first input line has an integer $t$: the number of tests.
After this, there are $t$ lines that describe the tests. Each line has eight integers $x_1$, $y_1$, $x_2$, $y_2$, $x_3$, $y_3$, $x_4$ and $y_4$.
Output
For each test, print "YES" if the line segments intersect and "NO" otherwise.
Constraints
- $1 \le t \le 10^5$
- $-10^9 \le x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4 \le 10^9$
- $(x_1,y_1) \neq (x_2,y_2)$
- $(x_3,y_3) \neq (x_4,y_4)$
Input:
5
1 1 5 3 1 2 4 3
1 1 5 3 1 1 4 3
1 1 5 3 2 3 4 1
1 1 5 3 2 4 4 1
1 1 5 3 3 2 7 4
Output:
NO
YES
YES
YES
YES