F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

套娃

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
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
 

Sample Output
Yes No
 

Hint
经过 Convex Checker 测试,我们的数据里没有凹包。
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-11-26 18:19:17, Gzip enabled