Line Segment Intersection

题目描述

有两条线段：第一条经过点 (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)$

标签: CSES2190|几何

来源

CSES2190|几何