你有 $n$ 个套娃,第 $i$ 个套娃可以表示为一个凸包 $P_i$。
称第 $i$ 个套娃可以装进第 $j$ 个套娃,当且仅当通过平移 $P_i$,其中的每一个点(包括边界)都在 $P_j$ 内部(不能在边界上)。
你需要报告给定的套娃序列是否满足:对于任意 $1≤i\lt j≤n$,要么第 $i$ 个套娃可以装进第 $j$ 个中,要么第 $j$ 个可以装进第 $i$ 个。
定义一个简单多边形 $P$ 为凸包,当且仅当 $P$ 的每一个内角都严格大于 $0$ 小于 $π$。
本题有多组数据。第一行一个正整数 $T(1≤T≤10032)$,表示测试数据组数。
对于每组数据,第一行输入一个整数 $n(2≤n≤10^5 )$,代表套娃个数。接下来输入 $n$ 个套娃。
对于每个套娃,第一行输入一个整数 $m(3≤m≤2⋅10^5 )$代表对应凸包的点数。接下来 $m$ 行以逆时针顺序给出凸包的顶点,第 $j$ 行两个整数 $x_j,y_j$ 表示第 $j$ 个顶点的坐标为 $(x_j,y_j)(1≤x_j,y_j≤10^9)$。
对于每组数据,保证 $∑m≤4⋅10^5$。
对于所有数据,保证 $∑n≤2⋅10^5, ∑m≤2.2⋅10^6$ 。
对于每组数据输出一行一个字符串。若给定的序列满足性质,则输出 Yes
,否则输出 No
。
2 4 4 1 10 1 1 10 1 10 10 3 1 2 7 1 4 5 3 2 2 3 2 2 3 4 3 3 1 3 1 1 3 1 3 3 1 1 3 1 1 3 3 1 2 3 1 2 3 3 1 1 2 1 1 2
\n \n \n · \n · \n · \n · \n \n · \n · \n · \n \n · \n · \n · \n \n · \n · \n · \n · \n \n \n · \n · \n · \n \n · \n · \n · \n \n · \n · \n · \n
Yes No
\n \n
经过 Convex Checker 测试,我们的数据里没有凹包。