변하지 않은 그림

시간 제한5초메모리 제한128 MB

요약

두 개의 플로터 명령어로 그려진 벡터 그림이 이동, 회전, 균일 크기 조절만으로 서로 같아지는지(대칭 반전은 불허) 판별합니다.

난이도: 어려움10점 중 8점
유형: 기하, 문자열 매칭, 수학
정답자: 아직 제출이 없습니다

문제

스테가노그래피는 메시지를 암호화하는 대신 어딘가에 숨겨서 보호하는 특별한 기법이다. 디지털 스테가노그래피의 한 방법은 디지털 이미지 안에 작은 정보를 숨기는 것이다. 이미지의 변형이 매우 작아 사람의 눈으로는 알아챌 수 없지만, 컴퓨터는 그 안에 숨겨진 정보(예: 텍스트 메시지)를 읽어낼 수 있다. 이 문제에서 여러분의 과제는 두 이미지를 비교하여 그러한 (아주 작을 수도 있는) 차이를 찾아내는 것이다.

이 문제에서는 벡터 그림을 다룬다. 프로그램은 두 개의 그림을 입력받아 두 그림이 같은 도형을 나타내는지 판정해야 한다. 기하학적으로 말하면, 두 그림이 서로 닮았는지, 즉 평행이동, 회전, 그리고 일정한 비율의 확대·축소(단, 대칭 반전(거울상)은 허용되지 않는다)만으로 한쪽을 다른 쪽으로 변환할 수 있는지를 판정하는 것이다.

입력

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 두 개의 벡터 그림을 담고 있다. 각 그림은 플로터(plotter) 장치를 위한 명령의 나열로 표현되며, 한 줄에 하나의 명령이 주어진다. 모든 명령은 대문자 한 글자로 시작하고, 이어서 공백 한 칸과 공백으로 구분된 두 정수 좌표가 온다. 글자는 "L"(선을 그린다) 또는 "M"(그리지 않고 이동한다)이다. 두 좌표는 선을 그을 위치, 또는 현재 위치를 옮길 위치를 나타낸다. 좌표는 항상 바로 앞 명령이 끝난 위치를 기준으로 한 상대 좌표이며, 첫 번째 명령은 (구체적으로 정해지지 않은) 어떤 시작점을 기준으로 한다.

각 그림의 마지막 명령 다음에는 글자 "E"(끝)만 있는 줄과 빈 줄이 온다. 마지막 테스트 케이스 다음에는 글자 "Q"(종료)만 있는 줄이 온다.

한 그림의 명령 개수는 0개 이상 1000개 이하이다. 어떤 명령도 두 좌표가 동시에 0이 되지는 않는다. 모든 (상대) 좌표의 절댓값은 최대 1000이다.

출력

각 테스트 케이스마다, 두 그림이 닮았으면 "YES"를, 닮지 않았으면 "NO"를 한 줄에 출력한다.

예제4

예제 1

입력

L 3 1
L 3 1
M 3 0
M 0 1
L -3 -1
E

L 1 0
L -1 0
E

L 1 0
L 0 1
E

L 1 0
L -1 -1
E

L 2 0
L 1 1
L 0 1
L 2 3
L 0 1
L -1 1
L -2 0
L -1 -1
L 0 -1
L 2 -3
M 1 0
L -2 0
M 2 0
L 0 -1
L -1 1
L -1 -1
L 0 1
E

L 2 -4
L 3 -1
L 2 1
L 1 -2
L -2 -1
L 1 3
L -3 1
L 2 1
L 1 -2
L 8 -1
L 2 1
L 1 3
L -2 4
L -3 1
L -2 -1
L -4 -7
E

Q

예상 출력

YES
NO
YES

예제 2
입력
```
L 2 0
E

L 0 5
E

Q
```
예상 출력
```
YES
```

예제 3

입력

L 1 0
L 0 1
L -1 0
L 0 -1
E

L 2 0
L 0 2
L -2 0
L 0 -2
E

L 1 0
L 0 1
L -1 0
L 0 -1
E

L 2 0
L 0 1
L -2 0
L 0 -1
E

Q

예상 출력

YES
NO

예제 4
입력
```
L 1 0
L 0 1
E

L 1 0
L 0 1
E

Q
```
예상 출력
```
YES
```