Polygonal Line Search

時間制限 : 1 sec, メモリ制限 : 65536 KB
英語版はこちら

Problem B: Polygonal Line Search

xy平面上に複数の折れ線がある. 別に与えられた1本の折れ線と同じ形状のも のをすべて,これらの折れ線の中から見つけ出したい.

1本の折れ線は,始点から終点までの頂点が順に座標の組で与えられている. 折れ線を構成する各線分はx軸またはy軸に平行であり,頂点では必ず90度向きを 変える. また,1本の折れ線の中で同じ点を2回以上通ることはない. xy平面内で回転および平行移動によって(拡大縮小や裏返しをせずに)重なり合う形状のみを同じ形状とみなす.始点から終点まで の頂点が逆順に指定されているものも同一とみなす.

図1に折れ線の例を示す.このうち,AとBのみが同じ形状であ る.

与えられた折れ線と同じ形状の折れ線の番号をすべて答えるプログラムを書きなさい.

図1: 折れ線の例

Input

入力は複数のデータセットからなる.最後のデータセットの直後に一つの0のみを含む行がある.

一つのデータセットは以下のように与えられる.

n
折れ線0
折れ線1
折れ線2
...
折れ線n
nは,探す対象の折れ線(折れ線1〜折れ線n)の本数である.nは整数 であり, 1 <= n <= 50 である. 折れ線0は探す元となる折れ線を表す.

1本の折れ線は以下のように与えられる. mは折れ線を構成する頂点の数である.mは整数であり,3 <= m <= 10 である. xiyi がそれぞれ頂点のx座標, y座標を示し,一つの空白で区切られる.xiyiは整数であり, -10000 < xi < 10000, -10000 <yi < 10000 である.

m
x1 y1
x2 y2
...
xm ym

Output

入力の各データセットに対して,探す元となる折れ線と同じ形状の 折れ線の番号(1〜n)を,小さい順に,1行に一つずつ出力しなさい.ただし,番号は前後に空白のような余分な文字を含まないこと.

一つのデータセットの終わりに "+" 5文字を連続して1行に出力すること.

Sample Input

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

Output for the Sample Input

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

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Tokyo, Japan, 2005-07-01
http://www2.teu.ac.jp/icpc/