L3-006 迎风一刀斩

Statement

Metadata

作者: 刘汝佳
单位: 北京尔宜居科技有限责任公司
代码长度限制: 16 KB
时间限制: 150 ms
内存限制: 64 MB

迎着一面矩形的大旗一刀斩下，如果你的刀够快的话，这笔直一刀可以切出两块多边形的残片。反过来说，如果有人拿着两块残片来吹牛，说这是自己迎风一刀斩落的，你能检查一下这是不是真的吗？

注意摆在你面前的两个多边形可不一定是端端正正摆好的，它们可能被平移、被旋转（逆时针90度、180度、或270度），或者被（镜像）翻面。

这里假设原始大旗的四边都与坐标轴是平行的。

输入格式

输入第一行给出一个正整数 $N$ （ $\le 20$ ），随后给出 $N$ 对多边形。每个多边形按下列格式给出：

$k\quad x_1\quad y_1\cdots x_k\quad y_k$

其中 $k$ （ $2 < k \le 10$ ）是多边形顶点个数； $(x_i, y_i)$ （ $0 \le x_i, y_i \le 10^8$ ）是顶点坐标，按照顺时针或逆时针的顺序给出。

注意：题目保证没有多余顶点。即每个多边形的顶点都是不重复的，任意3个相邻顶点不共线。

输出格式

对每一对多边形，输出YES或者NO。

输入样例

8
3 0 0 1 0 1 1
3 0 0 1 1 0 1
3 0 0 1 0 1 1
3 0 0 1 1 0 2
4 0 4 1 4 1 0 0 0
4 4 0 4 1 0 1 0 0
3 0 0 1 1 0 1
4 2 3 1 4 1 7 2 7
5 10 10 10 12 12 12 14 11 14 10
3 28 35 29 35 29 37
3 7 9 8 11 8 9
5 87 26 92 26 92 23 90 22 87 22
5 0 0 2 0 1 1 1 2 0 2
4 0 0 1 1 2 1 2 0
4 0 0 0 1 1 1 2 0
4 0 0 0 1 1 1 2 0

输出样例

YES
NO
YES
YES
YES
YES
NO
YES

Last update: May 4, 2022