선분 교차 판정
평면 위의 두 선분 $AB$와 $CD$가 주어진다.
두 선분이 한 점 이상을 공유하면 두 선분이 만난다고 한다.
끝점에서 만나는 경우와 같은 직선 위에서 겹치는 경우도 만나는 것으로 본다.
$Q$개의 쿼리에 대해 두 선분이 만나는지 판정하라.
입력
첫 번째 줄에 쿼리의 개수 $Q$가 주어진다. $(1 \leq Q \leq 10^6)$
두 번째 줄부터 $Q$개의 줄에 걸쳐 두 선분의 정보가 주어진다.
각 줄에는 $x_1,y_1,x_2,y_2,x_3,y_3,x_4,y_4$가 공백으로 구분되어 주어진다.
이는 각각 점 $A=(x_1,y_1)$, 점 $B=(x_2,y_2)$, 점 $C=(x_3,y_3)$, 점 $D=(x_4,y_4)$를 의미한다.
모든 좌표는 정수이며 $-10^9 \leq x_i,y_i \leq 10^9$이다.
출력
각 쿼리마다 두 선분이 만나면 Yes를, 그렇지 않다면 No를 한 줄에 하나씩 출력한다.
예제 입력 1
6 0 0 4 4 0 4 4 0 0 0 1 1 2 2 3 3 0 0 4 0 2 0 6 0 0 0 2 0 2 0 2 2 0 0 1 0 2 0 3 0 -1 -1 1 1 2 0 3 0
예제 출력 1
Yes No Yes Yes No No