#P2684. Polygonal Line Search

    ID: 1684 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>计算几何模拟其他排序Japan 2005 Domestic

Polygonal Line Search

描述

xyxy 平面上给出了多条多边形线。给定多边形线列表和模板,您必须找出与模板形状相同的多边形线。

多边形线由平行于 xx 轴或 yy 轴的几条线段组成。它由从起点到终点的顶点的 xyxy 坐标列表按顺序定义,并且始终在每个顶点处旋转 9090 度。一条多边形线不会两次通过同一点。当两条多边形线仅在 xyxy 平面内通过旋转和平移(即没有放大或翻转)彼此完全重叠时,它们具有相同的形状。从起点到终点以相反顺序给出的顶点与按顺序给出的顶点相同。

图 1 显示了多边形线的示例。在此图中,多边形线 AABB 具有相同的形状。

编写一个程序来回答与模板具有相同形状的多边形线。


输入

输入由多个数据集组成。输入的结尾由一行表示,该行包含一个零。

数据集如下:

nn

多边形线00

多边形线11

多边形线22

...

多边形线nn

nnxyxy 平面上搜索对象的多边形线数。nn 是一个整数,1n501 \leq n \leq 50。多边形线 0 表示模板。

多边形线如下:

mm

x1x1 y1y1

x2x2 y2y2

......

xmxm ymym

mm 是多边形线的顶点数(3m103 \leq m \leq 10)。xix_iyiy_i 用空格分隔,分别是顶点的 xx 坐标和 yy 坐标(10000<xi<10000-10000 < x_i < 1000010000<yi10000-10000 < y_i \leq 10000)。


输出

对于输入中的每个数据集,您的程序应按升序报告分配给与模板具有相同形状的多边形线的数字。每个数字必须写在单独的行中,不能有任何其他字符,例如前导或尾随空格。

必须在每个数据集的末尾排成一行五个连续的 +


输入数据 1

5
5
0 0
2 0
2 1
4 1
4 0
5
0 0
0 2
-1 2
-1 4
0 4
5
0 0
0 1
-2 1
-2 2
0 2
5
0 0
0 -1
2 -1
2 0
4 0
5
0 0
2 0
2 -1
4 -1
4 0
5
0 0
2 0
2 1
4 1
4 0
4
4
-60 -75
-60 -78
-42 -78
-42 -6
4
10 3
10 7
-4 7
-4 40
4
-74 66
-74 63
-92 63
-92 135
4
-12 22
-12 25
-30 25
-30 -47
4
12 -22
12 -25
30 -25
30 47
3
5
-8 5
-8 2
0 2
0 4
8 4
5
-3 -1
0 -1
0 7
-2 7
-2 16
5
-1 6
-1 3
7 3
7 5
16 5
5
0 1
0 -2
8 -2
8 0
17 0
0

输出数据 1

1
3
5
+++++
3
4
+++++
+++++

来源

日本 2005 国内