Problem:


Problem B: Polygonal Line Search

Multiple polygonal lines are given on the xy-plane.
Given a list of polygonal lines and a template,
you must find out polygonal lines
which have the same shape as the template.

A polygonal line consists of several line segments parallel to x-axis or
y-axis.  It is defined by a list of xy-coordinates of vertices from the start-point to the end-point in order,
and always turns 90 degrees at each vertex.
A single polygonal line does not pass the same point twice.

Two polygonal lines  have the same shape when they
fully overlap each other only with rotation and translation
within xy-plane (i.e. without magnification or a flip).
The vertices given in reverse order from the start-point to the end-point is the
same as that given in order.

Figure 1 shows examples of polygonal lines.
In this figure, polygonal lines A and B have the same shape.

Write a program that answers polygonal lines which have the same shape  as
the template.

  

  Figure 1: Polygonal lines 

Input

The input consists of multiple datasets.
The end of the input is indicated by a line which contains a zero.

A dataset is given as follows.

n

Polygonal line0

Polygonal line1

Polygonal line2

...

Polygonal linen

n is the number of polygonal lines for the object of search on
xy-plane.
n is an integer, and  1 <= n <= 50.
Polygonal line0 indicates the template.

A polygonal line is given as follows. 

m

x1 y1

x2 y2

...

xm ym

m is the number of the vertices of a polygonal line (3 <= m <= 10).

xi and yi, separated by a space,
are the x- and y-coordinates
 of a vertex, respectively (-10000 < xi < 10000, -10000 <yi < 10000). 

Output

 
For each dataset in the input, your program should report numbers assigned to the polygonal lines that have the same shape as the template, in ascending order.
Each number must be written in a separate line without any other characters such as leading or trailing spaces. 

 
Five continuous "+"s must be placed in a line at the end of each dataset.

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



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


Sample output:
1
3
5
+++++
3
4
+++++
+++++

Submission status: Wrong Answer

Solution code:
def is_same(A,B):
    for rot in range(2):
        for i in range(4):
            if A == B: return True
            B = [[y,-x] for x,y in B]
        B = [[x-B[-1][0],y-B[-1][-1]] for x,y in B][::-1]
    return False
    
while 1:
    n = int(raw_input())
    if n == 0: break
    m = int(raw_input())
    xy0 = [map(int,raw_input().split()) for _ in xrange(m)]
    xy0 = [[x-xy0[0][0],y-xy0[0][0]] for x,y in xy0]
    for i in xrange(n):
        m = int(raw_input())
        xy = [map(int,raw_input().split()) for _ in xrange(m)]
        xy = [[x-xy[0][0],y-xy[0][1]] for x,y in xy]
        if is_same(xy0,xy): print i
    print "+++++"

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

def rotate(L):
    return [[y, -x] for x, y in L]

def move(src, tgt):
    tmp = []
    for x, y in tgt:
        dx = x - src[0][0]
        dy = y - src[0][1]
        tmp.append([[mx-dx, my-dy] for mx, my in tgt])
    return tmp

def isSame(src, tgt):
    return sorted(src) in map(sorted,tgt)

f = lambda:map(int, raw_input().split())
while True:
    n = input()
    if n == 0: break
    src = [f() for i in range(input())]
    tgts = [[f() for i in range(input())] for i in range(n)]
    ans = []
    for i, tgt in enumerate(tgts):
        tmp = deepcopy(tgt)
        for j in range(4):
            if isSame(src, move(src, tmp)):
                ans.append(i + 1)
                break
            tmp = rotate(tmp)
    for a in ans:
        print a
    print '+' * 5

Submission status: Accepted

Solution code:
while 1:
  n=int(input())
  if n==0:
    break
  data=[[] for i in range(n+1)]
  for i in range(n+1):
    m=int(input())
    x,y=map(int,input().split())
    for j in range(m-1):
      _x,_y=map(int,input().split())
      data[i].append((abs(_x+_y-x-y),1 if x<_x else 3 if x>_x else 0 if y< _y else 2 ))
      x,y=_x,_y
  for i in range(1,n+1):
    d=[(e[0], (e[1]+(data[0][0][1]-data[i][0][1]))%4) for e in data[i]]
    f=[(e[0], (e[1]+(data[0][0][1]-data[i][-1][1]))%4) for e in data[i][::-1]]
    if data[0]==d:
      print(i)
    elif data[0]==f:
      print(i)
  print('+++++')

Submission status: Accepted

Solution code:
ans_list = []
while True:
    n = int(input())
    if not n:
        break
    xy = []
    for i in range(n + 1):
        xy.append([])
        m = int(input())
        x, y = map(int, input().split())
        for j in range(m - 1):
            a, b = map(int, input().split())
            xy[i].append([a - x, b - y])


        if 0 > xy[i][0][0]:
            for j in range(m - 1):
                this = xy[i][j]
                xy[i][j] = [this[0] * -1, this[1] * -1]
        elif 0 < xy[i][0][1]:
            for j in range(m - 1):
                this = xy[i][j]
                xy[i][j] = [this[1], this[0] * -1]
        elif 0 > xy[i][0][1]:
            for j in range(m - 1):
                this = xy[i][j]
                xy[i][j] = [this[1] * -1, this[0]]

    ans = []
    import copy
    check1 = copy.copy(xy[0])
    check2 = []
    for i in check1[::-1]:
        check2.append([i[1], i[0]])
    check2 += [[0, 0]]
    for i in range(1, len(check2)):
        check2[i][0] = check2[i][0] - check2[0][0]
        check2[i][1] = check2[i][1] - check2[0][1]
        check2[i][1] *= -1

    del check2[0]
    m = len(check2) + 1
    if 0 > check2[0][0]:
        for j in range(m - 1):
            this = check2[j]
            check2[j] = [this[0] * -1, this[1] * -1]
    elif 0 < check2[0][1]:
        for j in range(m - 1):
            this = check2[j]
            check2[j] = [this[1], this[0] * -1]
    elif 0 > check2[0][1]:
        for j in range(m - 1):
            this = check2[j]
            check2[j] = [this[1] * -1, this[0]]

    for i in range(1, n + 1):
        if check1 == xy[i] or check2 == xy[i]:
            ans.append(i)
    ans.append("+++++")
    ans_list.append(ans)

for i in ans_list:
    for j in i:
        print(j)

Submission status: Accepted

Solution code:
class Pline :
	def __init__(self, flag = False):
		self.m = int(raw_input())
		self.points = [map(int,raw_input().split(" ")) for i in range(self.m)]
		self.points_rev = self.points[::-1]
		self.points = self.opt(self.points)
		if flag:
			self.points_rev = self.opt(self.points_rev)
		
	def isSame (self, pline):
		return ( self.m == pline.m and (self.comp(self.points, pline.points) 
				 or self.comp(self.points_rev, pline.points)) )

	def opt(self, points):
		dzero = (0 - points[0][0],  0 - points[0][1])
		second = (points[1][0] + dzero[0], points[1][1] + dzero[1])
		if second[0] == 0:
			sign = - 1 if second[1] < 0 else 1
			points = [[sign*(x + dzero[0]), sign*(y + dzero[1])] for x, y in points]
		else :
			sign = - 1 if second[0] < 0 else 1
			points = [[-sign*(y + dzero[1]) ,sign*(x + dzero[0]) ] for x, y in points]
		return points

	def comp (self, points_a, points_b):
		for i in range(self.m):
			if points_a[i] != points_b[i]:
				break
		else :
			return True
		return False

while 1:
	n = int(raw_input())
	if n == 0:
		break
	same_list = []
	zero_pline = Pline(True)
	for i in range(1,n+1):
		pline = Pline()
		if zero_pline.isSame(pline):
			same_list.append(i)
	same_list.sort()
	for i in same_list:
		print i
	print "+++++"

Submission status: Accepted

Solution code:
def is_same(A,B):
    for rot in range(4):
        for i in range(4):
            if A == B: return True
            B = [[y,-x] for x,y in B]
        B = [[x-B[-1][0],y-B[-1][-1]] for x,y in B][::-1]
    return False
    
while 1:
    n = int(raw_input())
    if n == 0: break
    poly = []
    for loop in xrange(n+1):
        m = int(raw_input())
        xy = [map(int,raw_input().split()) for _ in xrange(m)]
        xy = [[x-xy[0][0],y-xy[0][1]] for x,y in xy]
        poly.append(xy)
    for i in xrange(1,n+1):
        if is_same(poly[0],poly[i]):
            print i
    print "+++++"

Submission status: Accepted

Solution code:
def is_same(A,B):
    for rot in range(2):
        for i in range(4):
            if A == B: return True
            B = [[y,-x] for x,y in B]
        B = [[x-B[-1][0],y-B[-1][-1]] for x,y in B][::-1]
    return False
    
while 1:
    n = int(raw_input())
    if n == 0: break
    poly = []
    for i in xrange(n+1):
        m = int(raw_input())
        xy = [map(int,raw_input().split()) for _ in xrange(m)]
        poly.append([[x-xy[0][0],y-xy[0][1]] for x,y in xy])
    for i in xrange(1,n+1):
        if is_same(poly[0],poly[i]):
            print i
    print "+++++"

Submission status: Accepted

Solution code:
def rot90(li):
    li2 = []
    for l in li:
        li2.append([l[0]*0+l[1]*(-1),l[0]*1+l[1]*0])
    return li2

while True:
    num_in = input()
    if num_in == 0:
        break
    pattern_list = []
    sam_li = []
    num = input()
    flagg = 1
    for j in range(num):
        x,y = map(int,raw_input().split())
        if flagg == 1:
            dxx,dyy = 0-x,0-y
        flagg = 0
        sam_li.append([x+dxx,y+dyy])
    dif_x = 0 -sam_li[num-1][0]
    dif_y = 0 -sam_li[num-1][1]
    sam_li2 = []
    for i in sam_li:
        sam_li2.append([i[0]+dif_x,i[1]+dif_y])
    sam_li2.reverse()
    pattern_list.append(sam_li)
    pattern_list.append(sam_li2)
    pattern_list.append(rot90(sam_li))
    pattern_list.append(rot90(sam_li2))
    pattern_list.append(rot90(rot90(sam_li)))
    pattern_list.append(rot90(rot90(sam_li2)))
    pattern_list.append(rot90(rot90(rot90(sam_li))))
    pattern_list.append(rot90(rot90(rot90(sam_li2))))
    for i in range(num_in):
        lis = []
        flag = 0
        for j in range(input()):
            x,y = map(int,raw_input().split())
            if flag == 0:
                xd, yd= 0-x,0-y
            flag = 1
            lis.append([x+xd,y+yd])
        if(lis in pattern_list):
            print i+1
    print "+++++"

Submission status: Accepted

Solution code:
import sys

def spin(x):
    result=[]
    for i in x:
        result.append([-1*i[1],i[0]])
    return result
def rev(x):
    y=x.copy()
    y.reverse()
    a=y[0][0]
    b=y[0][1]
    for i in y:
        i[0]-=a
        i[1]-=b
    return y

def check(x):
    if x==line_original or spin(x)==line_original or spin(spin(x))==line_original or spin(spin(spin(x)))==line_original:
        return True
    else:
        return False



while True:
    n=int(input())
    if n==0:
        sys.exit()

    m=int(input())
    line_original=[[0,0]]
    a,b=[int(i) for i in input().split(" ")]
    for count in range(m-1):
        p,q=[int(i) for i in input().split(" ")]
        line_original.append([p-a,q-b])
    line_list=[]
    for loop in range(n):
        m=int(input())
        line=[[0,0]]
        a,b=[int(i) for i in input().split(" ")]
        for count in range(m-1):
            p,q=[int(i) for i in input().split(" ")]
            line.append([p-a,q-b])
        line_list.append(line)

    for i in range(n):
        if (check(line_list[i])==True) or (check(rev(line_list[i]))==True):
            print(i+1)
    print("+++++")

Submission status: Accepted

Solution code:
def read_path():
    m = int(raw_input())
    return [complex(*[int(_) for _ in raw_input().split()]) for __ in xrange(m)]


def is_cong(p1, p2):
    l = len(p1)
    if l != len(p2):
        return False
    r = (p1[1] - p1[0]) / (p2[1] - p2[0])
    if r not in (1, 1j, -1, -1j):
        return False
    for i in xrange(1, l - 1):
        if (p1[i + 1] - p1[i]) / (p2[i + 1] - p2[i]) != r:
            return False
    return True


while True:
    n = int(raw_input())
    if n == 0:
        break
    p0 = read_path()
    p0r = list(reversed(p0))
    for i in xrange(1, n + 1):
        p = read_path()
        if is_cong(p0, p) or is_cong(p0r, p):
            print i
    print "+++++"

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(a):
        m = len(a)
        r = []
        if a[0][0] == a[1][0]:
            if a[0][1] < a[1][1]:
                r = [(a[i][0]-a[i+1][0], a[i][1]-a[i+1][1]) for i in range(m-1)]
            else:
                r = [(a[i+1][0]-a[i][0], a[i+1][1]-a[i][1]) for i in range(m-1)]
        else:
            if a[0][0] < a[1][0]:
                r = [(a[i+1][1]-a[i][1], a[i][0]-a[i+1][0]) for i in range(m-1)]
            else:
                r = [(a[i][1]-a[i+1][1], a[i+1][0]-a[i][0]) for i in range(m-1)]
        return tuple(r)

    while True:
        n = I()
        if n == 0:
            break

        a = []
        for _ in range(n+1):
            m = I()
            a.append([LI() for _ in range(m)])

        t = f(a[0])
        r = []
        for i in range(1,n+1):
            if t == f(a[i]) or t == f(a[i][::-1]):
                rr.append(i)

        rr.append('+++++')



    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def main():
    N = int(input())
    while N:
        lines = []
        for _ in range(N+1):
            tmp = []
            M = int(input())
            x0, y0 = map(int, input().split())
            x1, y1 = map(int, input().split())
            x2, y2 = map(int, input().split())
    
            L1 = abs(x0 + y0 - x1 - y1)
            L2 = abs(x1 + y1 - x2 - y2)
    
            v1 = [(x1-x0)//L1, (y1-y0)//L1]
            v2 = [(x2-x1)//L2, (y2-y1)//L2]
    
            tmp.append(str(L1))
            if [-v1[1], v1[0]] == v2:
                tmp.append("L")
            else:
                tmp.append("R")
            tmp.append(str(L2))
    
            for _ in range(M-3):
                x0, y0 = x1, y1
                x1, y1 = x2, y2
                x2, y2 = map(int, input().split())
    
                L1 = L2
                L2 = abs(x1 + y1 - x2 - y2)
    
                v1 = v2
                v2 = [(x2-x1)//L2, (y2-y1)//L2]
    
                if [-v1[1], v1[0]] == v2:
                    tmp.append("L")
                else:
                    tmp.append("R")
                tmp.append(str(L2))
            lines.append(tmp)
    
        base1 = "".join(lines[0])
    
        base2 = ""
        for l in lines[0][::-1]:
            if l == "L":
                base2 += "R"
            elif l == "R":
                base2 += "L"
            else:
                base2 += l
    
        for i, line in enumerate(lines[1:], start=1):
            l = "".join(line)
            if l == base1 or l == base2:
                print(i)
        print("+++++")
        N = int(input())

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def cross(a, b):
    return (a.real*b.imag - a.imag*b.real)

EPS = 10**(-7)

while 1:
    n = int(raw_input())
    if n == 0: break
    l0 = []
    d0 = []
    for i in xrange(n+1):
        l = []
        d = []
        p = []
        m = int(raw_input())
        for j in xrange(m):
            x,y = map(int, raw_input().split())
            p.append(x+y*1j)
        for j in xrange(1, m):
            if i == 0:
                l0.append(abs(p[j]-p[j-1]))
                if j > 1:
                    tmp = cross(p[j-1]-p[j-2], p[j]-p[j-1])
                    if tmp > EPS: d0.append(1)
                    else: d0.append(-1)
            else:
                l.append(abs(p[j]-p[j-1]))
                if j > 1:
                    tmp = cross(p[j-1]-p[j-2], p[j]-p[j-1])
                    if tmp > EPS: d.append(1)
                    else: d.append(-1)
        if i > 0:
            flag = False
            #print l0
            #print l
            if len(l0) == len(l):
                #print d0
                #print d
                if len(l0) != len(l):
                    break
                else:
                    for j in xrange(len(l)):
                        if l0[j] != l[j]:
                            break
                    else:
                        for k in xrange(len(d)):
                            if d0[k] != d[k]:
                                break
                        else:
                            flag = True
                    if flag is False:
                        for j in xrange(len(l)):
                            if l0[j] != l[len(l)-(j+1)]:
                                break
                        else:
                            for k in xrange(len(d)):
                                if (-1)*d0[k] != d[len(d)-(k+1)]:
                                    break
                            else:
                                flag = True
            if flag is True: print i
    print '+++++'

Submission status: Accepted

Solution code:
from copy import deepcopy
def rotate(L):
    return [[y, -x] for x, y in L]

def move(src, tgt):
    for x, y in tgt:
        dx = x - src[0][0]
        dy = y - src[0][1]
        tmp = [[mx-dx, my-dy] for mx, my in tgt]
        yield tmp
        yield list(reversed(tmp))

def isSame(src, tgt):
    return src == tgt

def compare(src, tmp):
    for tgt in move(src, tmp):
        if isSame(src, tgt):
            return True
    return False

f = lambda:map(int, raw_input().split())
while True:
    n = input()
    if n == 0: break
    src = [f() for i in range(input())]
    tgts = [[f() for i in range(input())] for i in range(n)]
    ans = []
    for i, tgt in enumerate(tgts):
        tmp = deepcopy(tgt)
        for j in range(4):
            if compare(src, tmp):
                ans.append(i + 1)
                break
            tmp = rotate(tmp)
    for a in ans:
        print a
    print '+' * 5

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

'''

'''

def func():
    '''

    '''
    while True:
        n = int(raw_input())
        if n == 0:
            break

        # line_0
        m = int(raw_input())
        standard_positions = []
        standard_lines = []
        standard_reverse_lines = []

        for pos_num in range(m):
            x, y = map(int, raw_input().split())
            standard_positions.append([x, y])

        for num in range(m-1):
            line = [0, 0]
            if standard_positions[num][0] < standard_positions[num+1][0]:
                line = [0, standard_positions[num+1][0] - standard_positions[num][0]]
            elif standard_positions[num][0] > standard_positions[num+1][0]:
                line = [2, standard_positions[num][0] - standard_positions[num+1][0]]
            else:
                if standard_positions[num][1] < standard_positions[num+1][1]:
                    line = [1, standard_positions[num+1][1] - standard_positions[num][1]]
                elif standard_positions[num][1] > standard_positions[num+1][1]:
                    line = [3, standard_positions[num][1] - standard_positions[num+1][1]]
            standard_lines.append(line)

        for index in range(len(standard_lines)):
            reverse_line = [(standard_lines[-1-index][0] + 2) % 4, standard_lines[-1-index][1]]
            standard_reverse_lines.append(reverse_line)

        # print standard_positions
        # print standard_lines
        # print standard_reverse_lines

        # line_1 - line_n
        for data_num in range(n):
            m = int(raw_input())
            positions = []
            lines = []
            for pos_num in range(m):
                x, y = map(int, raw_input().split())
                positions.append([x, y])
            for num in range(m-1):
                line = [0, 0]
                if positions[num][0] < positions[num+1][0]:
                    line = [0, positions[num+1][0] - positions[num][0]]
                elif positions[num][0] > positions[num+1][0]:
                    line = [2, positions[num][0] - positions[num+1][0]]
                else:
                    if positions[num][1] < positions[num+1][1]:
                        line = [1, positions[num+1][1] - positions[num][1]]
                    elif positions[num][1] > positions[num+1][1]:
                        line = [3, positions[num][1] - positions[num+1][1]]
                lines.append(line)

            for offset in range(4):
                for line in lines:
                    line[0] = (line[0] + offset) % 4
                if lines == standard_lines or lines == standard_reverse_lines:
                    print data_num + 1
            
        print '+++++'
            


                        

    return None

if __name__ == '__main__':
    func()

Submission status: Accepted

Solution code:
class Line:
    def __init__(self, n, points):
        self.n = n
        self.points = points

    def getDesc(self):
        desc1 = self.getDist(self.points[0], self.points[1])
        faceDir = self.getDir(self.points[0], self.points[1])
        for i in range(1, self.n - 1):
            newDir = self.getDir(self.points[i], self.points[i+1])
            desc1 += self.getTurn(faceDir, newDir)
            desc1 += self.getDist(self.points[i], self.points[i+1])
            faceDir = newDir

        desc2 = self.getDist(self.points[-1], self.points[-2])
        faceDir = self.getDir(self.points[-1], self.points[-2])
        for i in range(self.n - 2, 0, -1):
            newDir = self.getDir(self.points[i], self.points[i-1])
            desc2 += self.getTurn(faceDir, newDir)
            desc2 += self.getDist(self.points[i], self.points[i-1])
            faceDir = newDir

        return sorted([desc1, desc2])

    def getTurn(self, origDir, destDir):
        if origDir == 'N':
            if destDir == 'E':
                return '1'
            elif destDir == 'S':
                return '2'
            elif destDir == 'W':
                return '3'
        if origDir == 'E':
            if destDir == 'S':
                return '1'
            elif destDir == 'W':
                return '2'
            elif destDir == 'N':
                return '3'
        if origDir == 'S':
            if destDir == 'W':
                return '1'
            elif destDir == 'N':
                return '2'
            elif destDir == 'E':
                return '3'
        if origDir == 'W':
            if destDir == 'N':
                return '1'
            elif destDir == 'E':
                return '2'
            elif destDir == 'S':
                return '3'
        
    def getDir(self, p1, p2):
        if p1[1] < p2[1]:
            return 'N'
        if p1[0] < p2[0]:
            return 'E'
        if p1[0] > p2[0]:
            return 'W'
        if p1[1] > p2[1]:
            return 'S'

    def getDist(self, p1, p2):
        if p1[0] != p2[0]:
            return str(abs(p1[0] - p2[0]))
        return str(abs(p1[1] - p2[1]))

def getPolyLine():
    n = int(input())
    points = []
    for _ in range(n):
        x, y = list(map(int, input().strip().split()))
        points.append( (x, y) )
    return Line(n, points)

if __name__ == '__main__':
    while True:
        N = int(input())
        if N == 0:
            break

        polyLine = getPolyLine()
        template = polyLine.getDesc()
        P = polyLine.n

        for idx in range(1, N + 1):
            polyLine = getPolyLine()
            desc = polyLine.getDesc()
            if polyLine.n == P and desc[0] == template[0] and desc[1] == template[1]:
                print(idx)

        print("+++++")

Submission status: Accepted

Solution code:
from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return


def main():
    while(1):
        N = int(input())
        if N == 0:
            break
        lines = [0] * (N+1)
        for i in range(N+1):
            M = int(input())
            # はじめはべつに
            line = [list(map(int,input().split()))]
            par = line[0].copy()
            line[0][0] -= par[0]
            line[0][1] -= par[1]
            for _ in range(M-1):
                line.append(list(map(int,input().split())))
                line[-1][0] -= par[0]
                line[-1][1] -= par[1]
            lines[i] = line
        # print(lines)
        # i が見るの
        for i in range(1, N+1):
            # はじめと終わりを反転
            for __ in range(2):
                for _ in range(4):
                    if lines[0] == lines[i]:
                        print(i)
                        # ans += 1
                        break
                    for j in range(len(lines[i])):
                        lines[i][j][0], lines[i][j][1] = lines[i][j][1], -lines[i][j][0]
                lines[i] = lines[i][::-1]
                # print(lines[i])
                par = lines[i][0].copy()
                lines[i][0][0] -= par[0]
                lines[i][0][1] -= par[1]
                for j in range(1, len(lines[i])):
                    lines[i][j][0] -= par[0]
                    lines[i][j][1] -= par[1]
        print("+++++")
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def check(a, b):
    for _ in range(4):
        if a == b:
           return True
        b = list(map(lambda x: [-x[1], x[0]], b))
    return False
def main(n):
    lines = [None] * n
    for i in range(n):
        m = int(input())
        xy = [None] * m
        for j in range(m):
            xy[j] = list(map(int, input().split()))
        lines[i] = xy
    x, y = lines[0][0]
    ans = list(map(lambda z: [z[0] - x, z[1] - y], lines[0]))
    for num, line in enumerate(lines[1:]):
        x, y = line[0]
        fline = list(map(lambda z: [z[0] - x, z[1] - y], line))
        x, y = line[-1]
        eline = list(map(lambda z: [z[0] - x, z[1] - y], line[::-1]))
        if check(ans, fline) or check(ans, eline):
            print(num+1)
    print("+" * 5)



while 1:
    n = int(input())
    if n == 0:
        break
    main(n + 1)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def calc_ar(bx,by,x,y):
    if bx == x:
        if y > by:
            return 1
        else:
            return 3
    else:
        if x > bx:
            return 0
        else:
            return 2

while True:
    N = inp()
    if N == 0:
        break
    else:
        lines = []

        for _ in range(N+1):
            m = inp()
            xys = [inpl() for _ in range(m)]

            dd = []
            for i in range(1,m):
                bx,by = xys[i-1]
                x,y = xys[i]
                if x == bx:
                    dd.append(abs(y-by))
                else:
                    dd.append(abs(x-bx))

            ar = []
            for i in range(2,m):
                x0,y0 = xys[i-2]
                x1,y1 = xys[i-1]
                x2,y2 = xys[i]
                ar01 = calc_ar(x0,y0,x1,y1)
                ar12 = calc_ar(x1,y1,x2,y2)
                ar.append((ar12 - ar01)%4)

            lines.append([dd]+[ar])


        for i in range(1,N+1):
            dd,ar = lines[i]
            if lines[0] == [dd]+[ar]:
                print(i)
            else:
                dd = list(reversed(dd))
                ar = [(a+2)%4 for a in reversed(ar)]
                if lines[0] == [dd]+[ar]:
                    print(i)



        print('+++++')

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    N = int(input())
    if N == 0:
        exit()
    n = int(input())
    true_Poly = [list(map(int, input().split())) for _ in range(n)]

    serach_Polys = []
    for _ in range(N):
        n = int(input())
        serach_Polys.append([list(map(int, input().split()))
                             for _ in range(n)])

    ans = []
    for i, poly in enumerate(serach_Polys):
        if is_same(true_Poly, poly):
            ans.append(i+1)
    if ans:
        print("\n".join(map(str, ans)))
    print("+"*5)


def is_same(poly1, poly2):
    if len(poly1) != len(poly2):
        return False

    poly_1_turn = calc_turn(poly1)
    poly_1_len = calc_dist(poly1)

    poly_2_turn = calc_turn(poly2)
    poly_2_len = calc_dist(poly2)
    if all(a == b for a, b in zip(poly_2_turn, poly_1_turn)) and all(a == b for a, b in zip(poly_2_len, poly_1_len)):
        return True

    poly_2_rev_turn = calc_turn(list(reversed(poly2)))
    poly_2_rev_len = calc_dist(list(reversed(poly2)))
    if all(a == b for a, b in zip(poly_2_rev_turn, poly_1_turn)) and all(a == b for a, b in zip(poly_2_rev_len, poly_1_len)):
        return True
    return False


def dist(p1, p2):
    return sum([abs(x1-x2) for x1, x2 in zip(p1, p2)])


def calc_dist(poly):
    return [dist(p1, p2) for p1, p2 in zip(poly, poly[1:])]


def turn(p1, p2, p3):
    """
    右回りが1 左が-1
    """
    if p1[0] == p2[0]:
        if p1[1] < p2[1]:
            if p3[0] > p2[0]:
                return 1
            else:
                return 0
        else:
            if p3[0] > p2[0]:
                return 0
            else:
                return 1
    else:
        if p1[0] < p2[0]:
            if p3[1] > p2[1]:
                return 0
            else:
                return 1
        else:
            if p3[1] > p2[1]:
                return 1
            else:
                return 0


def calc_turn(poly):
    return [turn(p1, p2, p3) for p1, p2, p3 in zip(poly, poly[1:], poly[2:])]


while True:
    solve()

Submission status: Accepted

Solution code:
# coding: utf-8
while 1:
    n=int(input())
    if n==0:
        break
    data=[[] for i in range(n+1)]
    for i in range(n+1):
        m=int(input())
        x,y=map(int,input().split())
        for j in range(m-1):
            _x,_y=map(int,input().split())
            data[i].append((abs(_x+_y-x-y),1 if x<_x else 3 if x>_x else 0 if y<_y else 2))
            x,y=_x,_y
    for i in range(1,n+1):
        d=[(e[0],(e[1]+(data[0][0][1]-data[i][0][1]))%4) for e in data[i]]
        f=[(e[0],(e[1]+(data[0][0][1]-data[i][-1][1]))%4) for e in data[i][::-1]]
        if data[0]==d:
            print(i)
        elif data[0]==f:
            print(i)
    print('+++++')