题目描述

棱堡（Bastion）是第一种仅靠直射火力而不存在攻击死角的堡垒。

简单非退化多边形是由 $n$ ($n\ge 3$) 个顶点序列组成的闭合多边形 区域，满足以下条件：

• 顶点序列首尾相连，形成 $n$ 条边，构成平面紧致闭集（含所有边界和内部点）；
• $n$ 条边仅在顶点处相接且互不相交（相邻边在公共顶点外无其他交点）；
• $n$ 个顶点互不重合，且不位于任何非相邻边的内部，且任意三个连续的顶点不共线。

棱堡可以被视为由 $n$ 个点和 $n$ 条边组成的简单非退化多边形。对于多边形边上互异两点 $P$ 和 $Q$，我们定义点 $P$ 可以火力直射点 $Q$，当且仅当线段 $PQ$ 与多边形只交于 $P$ 和 $Q$ 两点。如下图所示，点 $A$ 和 $B$ 不能火力直射点 $X$，但是点 $C$ 可以。如果对于多边形边上一点 $P$，不存在多边形边上另外一点 $Q$ 使得点 $Q$ 可以火力直射 $P$，则我们称点 $P$ 为该多边形的火力盲区。

我们称一个简单非退化多边形是棱堡，当且仅当其至多存在有限个点是火力盲区。给定一个简单非退化多边形，请判断其是否是一个棱堡。

形式化而言，给定一个简单非退化多边形，请判断其是否只有有限个位于多边形边上的点 $P$ 满足，不存在多边形边上的另外一点 $Q$，使得 $PQ$ 线段与多边形的交集只包含 $P$ 和 $Q$。

输入格式

输入包含多组测试用例。数据的第一行包含一个整数 $t$ ($1 \leq t \leq 10^4$) 表示测试用例数。接下来描述每个测试用例。

每个测试用例的第一行包含一个整数 $n$ ($3 \leq n \leq 10^5$)，为多边形的边数。

接下来 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($-10^9 \leq x_i, y_i \leq 10^9$)，描述多边形的一个顶点。

输入数据保证构成简单非退化多边形。顶点以逆时针顺序给出，即按顺序走过所有顶点后恰好逆时针旋转 $360^\circ$。按顶点的输入顺序依次连边（第 $i$ 个顶点连向第 $i + 1$ 个顶点，第 $n$ 个顶点连回第 $1$ 个顶点）。

保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出仅包含一行一个字符串，如果多边形是棱堡，输出 $\tt{YES}$，否则输出 $\tt{NO}$。答案对大小写不敏感。

2
20
7 5
9 5
13 13
5 9
5 7
-5 7
-5 9
-13 13
-9 5
-7 5
-7 -5
-9 -5
-13 -13
-5 -9
-5 -7
5 -7
5 -9
13 -13
9 -5
7 -5
4
1 1
-1 1
-1 -1
1 -1

YES
NO