5073.套娃

时间限制:4s 内存限制:512MB

你有 $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 测试,我们的数据里没有凹包。

来源: 2024“钉耙编程”中国大学生算法设计超级联赛(10)

提交题解

Please login first.

© 2025 FAQs