|
||||||||||
套娃Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 13 Accepted Submission(s): 2 Problem Description 你有 $n$ 个套娃,第 $i$ 个套娃可以表示为一个凸包 $P_i$。 称第 $i$ 个套娃可以装进第 $j$ 个套娃,当且仅当通过平移 $P_i$,其中的每一个点(包括边界)都在 $P_j$ 内部(不能在边界上)。 你需要报告给定的套娃序列是否满足:对于任意 $1\le i < j\le n$,要么第 $i$ 个套娃可以装进第 $j$ 个中,要么第 $j$ 个可以装进第 $i$ 个。 定义一个简单多边形 $P$ 为凸包,当且仅当 $P$ 的每一个内角都严格大于 $0$ 小于 $\pi$。 Input 本题有多组数据。第一行一个正整数 $T$($1\le T\le 10032$),表示测试数据组数。 对于每组数据,第一行输入一个整数 $n$($2\le n\le 10^5$),代表套娃个数。接下来输入 $n$ 个套娃。 对于每个套娃,第一行输入一个整数 $m$($3\le m\le 2\cdot 10^5$)代表对应凸包的点数。接下来 $m$ 行以逆时针顺序给出凸包的顶点,第 $j$ 行两个整数 $x_j,y_j$ 表示第 $j$ 个顶点的坐标为 $(x_j,y_j)$($1\le x_j,y_j\le 10^9$)。 对于每组数据,保证 $\sum m \le 4\cdot 10^5$。 对于所有数据,保证 $\sum n \le 2\cdot 10^5$,$\sum m\le 2.2\cdot 10^6$。 Output 对于每组数据输出一行一个字符串。若给定的序列满足性质,则输出 `Yes`,否则输出 `No`。 Sample Input
Sample Output
Hint 经过 Convex Checker 测试,我们的数据里没有凹包。 Source | ||||||||||
|