CSES2190 线段相交
#CS2190. 线段相交
线段相交
题目背景
翻译自 CSES-2190 题。
题目描述
有两条线段：第一条线段通过点 (x1,y1)(x_1, y_1)(x1,y1) 和 (x2,y2)(x_2, y_2)(x2,y2)，第二条线段通过点 (x3,y3)(x_3, y_3)(x3,y3) 和 (x4,y4)(x_4, y_4)(x4,y4)。
你的任务是判断这两条线段是否相交，也就是说，它们是否至少有一个公共点。
输入格式
第一行输入一个整数 t t t，表示测试用例的数量。
接下来的 t t t 行每行包含六个整数：x1,y1,x2,y2,x3,y3 x_1, y_1, x_2, y_2, x_3, y_3 x1,y1,x2,y2,x3,y3，分别表示点 p1 p_1 p1, p2 p_2 p2, 和 p3 p_3 p3 的坐标。
输出格式
第一行输入一个整数 t，表示测试用例的数量。
接下来的 t 行，每行包含八个整数：x1,y1,x2,y2,x3,y3,x4,y4x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4x1,y1,x2,y2,x3,y3,x4,y4，分别表示两条线段的端点坐标。
样例
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
说明/提示
$-10^9 \leq x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4 \leq 10^9$
(x1,y1)≠(x2,y2) (x_1, y_1) \neq (x_2, y_2)(x1,y1)=(x2,y2)；
(x3,y3)≠(x4,y4)(x_3, y_3) \neq (x_4, y_4)(x3,y3)=(x4,y4)。