QOJ.ac

QOJ

时间限制: 10 s 内存限制: 524288 MB 总分: 100 可 Hack ✓

#14027. Pizza

统计

小 Vitechka 找到了一份送外卖的工作。当他开始工作时,他发现了一个问题:他工作的公司生产的披萨和包装盒形状非常奇特。它们的形状可以是任意的凸多边形。为了开始配送,Vitechka 必须把所有的披萨都装进它们的包装盒里。在此过程中,他不能翻转披萨(但他可以旋转它们)。

请帮助 Vitechka 解决这个问题。对于每个披萨,判断是否可以将其放入包装盒中,如果可以,找出具体的方法。

输入格式

第一行包含一个整数 $t$ ($1 \le t$),表示披萨的数量。接下来是 $t$ 个数据块。每个数据块描述一个披萨和它的包装盒。

每个数据块的第一行包含一个整数 $n$ ($3 \le n \le 30$),表示描述披萨形状的多边形的顶点数。接下来的 $n$ 行,每行包含两个绝对值不超过 $10^6$ 的实数,表示该多边形一个顶点的坐标。顶点按逆时针顺序给出。下一行包含一个整数 $m$ ($3 \le m \le 30$),表示描述包装盒形状的多边形的顶点数。随后以相同的格式给出包装盒形状的描述。

输入中的所有实数在小数点后最多包含 20 位数字。

所有多边形的顶点总数不超过 $10^3$。

保证如果将一个数据块中的每个点向任意方向移动最多 $10^{-3}$ 的距离,测试数据仍然是正确的,且披萨是否能放入包装盒的属性不会改变。

输出格式

对于每个数据块,如果无法将披萨放入包装盒中,则在单行中输出 “NO”。否则,在第一行输出 “YES”,在第二行输出三个实数,描述披萨的运动。第一个数必须是披萨绕原点旋转的角度(弧度)。第二和第三个数是随后披萨需要移动的向量的坐标。在应用所述运动后,披萨应该能放入包装盒中。如果披萨的每个顶点到包装盒的距离都不超过 $10^{-3}$,则认为披萨在包装盒内。

样例

输入样例 1

2
3
0 0
2 0
0 2
3
3 0
3 3
0 3
3
3 0
3 3
0 3
3
0 0
2 0
0 2

输出样例 1

NO
YES
3.1415926 3 3

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.