题目背景

翻译自 CSES-2190 题。

题目描述

有两条线段：第一条线段通过点 $(x_1, y_1)$ 和 $(x_2, y_2)$，第二条线段通过点 $(x_3, y_3)$ 和 $(x_4, y_4)$。

你的任务是判断这两条线段是否相交，也就是说，它们是否至少有一个公共点。

输入格式

第一行输入一个整数 $t$，表示测试用例的数量。

接下来的 $t$ 行每行包含六个整数：$x_1, y_1, x_2, y_2, x_3, y_3$，分别表示点 $p_1$, $p_2$, 和 $p_3$ 的坐标。

输出格式

第一行输入一个整数 $t$，表示测试用例的数量。

接下来的 $t$ 行，每行包含八个整数：$x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4$，分别表示两条线段的端点坐标。

样例

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

NO
YES
YES
YES
YES

说明/提示

$1 \leq t \leq 10^5$；

$-10^9 \leq x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4 \leq 10^9 $；

$(x_1, y_1) \neq (x_2, y_2)$；

$(x_3, y_3) \neq (x_4, y_4)$。