链接: https://cses.fi/problemset/task/2190

板块: Geometry

时限: 1.00 s ｜ 内存: 512 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 \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)$

样例输入

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