7417. 线段相交 (Line Segment Intersection)
时间限制：1000 MS 内存限制：512 MB
题目描述
# 线段相交 (Line Segment Intersection) 时间限制：$1.00\text{ s}$ 空间限制：$512\text{ MB}$ ## 题目描述 有两条线段：第一条线段连接点 $(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`。 ## 输入输出样例 ### 输入 #1 ```text 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 ``` ### 输出 #1 ```text 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)$