2641 다각형그리기

문제

모눈종이에 다각형을 그리려고 한다. 그리는 방법은 모양수열로 표시된다. 모양수열은 1과 4사이의 숫자가 연속되어 나열된 것으로 1은 오른쪽으로, 2는 위쪽으로, 3은 왼쪽으로, 4는 아래쪽으로 한 칸씩 그리는 것을 말한다.

예를 들어 아래 그림의 다각형 (2)는 점 A에서 시작하여 화살표 방향으로 모양수열 1411433322를 따라서 그린 것이다. 다각형 (3)은 점 B에서 시작하여 화살표 방향으로 모양수열 3221411433을 따라서 그린 것이다. 또한 다각형(4)는 점 C에서 시작하여 화살표 방향으로 모양수열 4411123323을 따라서 그린 것이다. 다각형 (2), (3), (4)는 다각형 (1)과 같으므로 모양수열들 1411433322, 3221411433, 4411123323은 모두 같은 다각형을 그릴 수 있다. 단, 다각형이 회전된 것이나 뒤집어진 것은 같은 다각형이 아니다. 그러므로 아래 그림의 다각형 (5)와 (6)은 다각형 (1)과 다르다.

한 개의 표본 모양수열과 여러 모양수열들이 주어졌을 때 표본 모양수열과 같은 다각형을 그릴 수 있는 모양수열들을 모두 찾는 프로그램을 작성하시오.

입력

첫째 줄에는 표본 모양수열의 길이(숫자의 개수)가 주어지고, 둘째 줄에는 표본 모양수열이 주어진다. 셋째 줄에는 모양수열의 개수가 주어지고 넷째 줄부터는 각 줄에 표본 모양수열과 같은 길이의 모양수열이 하나씩 주어진다. 단, 모양수열들의 개수는 최대 100 개이고 모양수열의 길이는 최대 50 이다. 모양수열의 각 숫자 사이에는 빈칸이 하나 있다.

출력

첫째 줄에는 입력된 표본 모양수열과 같은 다각형을 그리는 모양수열들의 개수를 출력한다. 둘째 줄부터는 각 줄에 표본 모양수열과 같은 다각형을 그릴 수 있는 모양수열을 출력한다. 출력되는 모양수열의 숫자들은 한 칸 띄고 출력한다.

풀이

  1. 1,2,3,4 가 상,우,하,좌 순으로 진행한다.
  2. [0,0]에서 시작한 값이 우측으로 한칸 가면 [1,0]이다
  3. 하나의 입력 리스트는 이러한 값들을 저장한 리스트를 갖게 된다. => list
  4. 똑같게 생긴 그림은 같은 위치에 있을 수도 있고, 다른 위치에 있을 수도 있다.
  5. list 를 x,y 순으로 정렬할 수 있다.
  6. 맨 앞의 값이 도형의 왼쪽 맨위 포인트가 된다. =>왼좌
  7. 기준의 왼좌 한 점과 , 비교하는 도형의 왼좌 차이 만큼 이동시켜준다
import sys
sys.stdin = open('input.txt')

N = int(input())
sample = list(map(int,input().split()))
M = int(input())
graph = []
for _ in range(M):
    tmp = list(map(int,input().split()))
    graph.append(tmp)



def square(list):
    dy = [0, 0, -1, 0, 1]
    dx = [0, 1, 0, -1, 0]
    point = []
    start = [0, 0]
    point.append(start)

    for i in list:
        ny = dy[i] + start[0]
        nx = dx[i] + start[1]
        start = [ny,nx]
        point.append(start)
    point.pop()
    return point


def sortsquare(list):
    list.sort(key=lambda x: (x[0]))
    list.sort(key=lambda x: (x[1]))
    return list

sample_square = sortsquare(square(sample))

rrr =[]

for g in graph:
    sortthis = sortsquare(square(g))
    result = []
    y = sample_square[0][0]-sortthis[0][0]
    x = sample_square[0][1]-sortthis[0][1]

    for [i,j] in sortthis:
        result.append([i+y,j+x])
    if sample_square == result:
        rrr.append(g)

print(len(rrr))
for i in rrr:
    print(*i)

좋은 웹페이지 즐겨찾기