아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

그림 검증기

시간 제한1초메모리 제한256 MB

요약
로봇 명령으로 그린 두 선 그림이 평행이동으로 일치하는지 판정합니다.
난이도

보통10점 중 7점

유형
기하, 구간, 정렬
정답자
아직 제출이 없습니다

문제

로봇 그리기 대회에서는 다음 두 명령으로 이루어진 프로그램으로 그림 하나를 그린다. 로봇은 그림의 시작점에서 출발한다.

  • L Xrel Yrel: 현재 위치에서 상대 좌표만큼 떨어진 점까지 선분을 그린다. 로봇은 그 선분의 끝점으로 이동한다.
  • M Xrel Yrel: 선을 그리지 않고 현재 위치만 상대 좌표만큼 옮긴다.

상대 좌표가 (0,0)(0, 0)인 L 명령은 길이가 0이라 아무것도 그리지 않는다.

대회 제출물은 기계가 자동으로 채점한다. 정답이 여러 개인 문제에서는 제출된 결과와 심사진이 준비한 정답을 비교해 판정하는 별도의 프로그램, 즉 검증기가 필요하다. 이 문제에서는 위 그리기 문제의 검증기를 만든다.

두 그림은 눈에 보이는 선이 같으면 같은 그림이다. 명령은 서로 달라도 된다. 선분 하나를 여러 개의 짧은 선분으로 나누어 그려도 되고, 같은 자리를 여러 번 덧그려도 된다. 각 그림이 덮는 점의 집합을 생각하자. 어떤 평행 이동으로 첫 번째 집합을 두 번째 집합과 완전히 일치시킬 수 있으면, 그리고 그럴 때만 두 그림은 같다. 따라서 크기가 다르거나 회전한 그림은 서로 다른 그림이다. 선분을 하나도 그리지 않은 그림끼리는 같은 그림이다.

입력

입력은 여러 개의 테스트 케이스로 이루어지고, 테스트 케이스는 20개를 넘지 않는다. 각 테스트 케이스는 그림 두 개로 이루어진다.

각 그림은 명령의 개수 NN (1≤N≤50001 \le N \le 5000)이 적힌 줄로 시작한다. 이어지는 NN개의 줄에 명령이 한 줄에 하나씩 주어진다. 각 명령은 대문자 하나, 공백 하나, 정수 XiX_i, 공백 하나, 정수 YiY_i로 이루어진다 (∣Xi∣≤1000|X_i| \le 1000, ∣Yi∣≤1000|Y_i| \le 1000). 대문자는 L 또는 M이다.

각 테스트 케이스 뒤에는 빈 줄이 하나 있다. 마지막 테스트 케이스 뒤에는 빈 줄이 없을 수도 있다. 로봇의 절대 좌표는 그림의 시작점에서 어느 방향으로도 30000을 넘지 않는다.

출력

각 테스트 케이스마다 한 줄씩 출력한다. 두 그림이 같으면 YES를, 다르면 NO를 출력한다.

예제2

  1. 예제 1

    입력
    2
    L 1 1
    L 1 1
    1
    L -2 -2
    
    2
    L 1 1
    L 1 1
    1
    L 3 3
    
    5
    L 1 0
    L 1 0
    L 0 5
    L 0 -5
    L 2 0
    3
    L 0 5
    M -2 -5
    L 4 0
    
    예상 출력
    YES
    NO
    YES
    
  2. 예제 2

    입력
    3
    M 5 5
    L 0 0
    M 1 1
    1
    M 3 -3
    
    2
    L 2 0
    L 0 2
    2
    L 0 2
    L 2 0
    
    
    예상 출력
    YES
    NO