题目背景

翻译自 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, x_4, y_4$，分别表示两条线段的端点坐标。

输出格式

对于每个测试用例，如果两条线段相交，输出 YES；否则输出 NO。

样例

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 \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)$