Czech ACM Student Chapter

Czech Technical University in Prague

Charles University in Prague

Technical University of Ostrava

acm

ˇ a

Slovak University of Technology

Pavol Jozef Saf´rik University in Koˇice

s

cz

ˇ

University of Zilina

Masaryk University

Matej Bel University in Bansk´ Bystrica

a

University of West Bohemia

CTU Open Contest 2014

Picture Validator

validate.c, validate.cpp, Validate.java

Karel wants to register his robot Karel for a robot contest. The aim of the contest is to draw

a picture using a program composed of the following instructions:

· L Xrel Yrel -- draw a line segment between the current robot position and the given relative

coordinates. The robot moves to the end point of the segment.

· M Xrel Yrel ­ move the current position by the given relative offset without drawing a line.

This sounds like a nice contest problem, doesn't it? We want to give you an idea what it is like

to organize a programming contest. All contests held at the Czech Technical University (since

the very first one on May 13, 1995) always employed the automated judging of submissions. The

output of a contestants' program is compared with the correct answer by a computer, without

the need of human intervention. This may seem obvious today but we should realize that back

in the old years, many programming contests in the world used human judges to issue the final

verdict. Manual judging then continued for many years in many other regions.

With some contest problems, there is more than one correct answer. In these cases, a special

program (called validator ) has to be prepared to review the submission output and to issue

a final verdict. Do you want to try out what it is like to write such a program?

Your task is to prepare a validator for the problem described above. The validator reads a picture

generated by a contestants' submission and decides whether it is equivalent to another picture

-- the correct answer prepared by judges.

Two pictures are considered equivalent if they are composed of the same visible line segments.

Note however that the drawing instructions may differ. For instance, some of the segments may

be divided into several shorter segments, or even drawn repeatedly. Also note that pictures with

a different scale or rotation are considered different.

Input Specification

The input contains several test cases. Each test case consists of two pictures. Each picture starts

with a row containing one positive integer N , the number of drawing instructions to follow

(1 ≤ N ≤ 5000). Then there are N lines, each containing one instruction. The instruction

consists of an uppercase letter, one space and two integers Xi, Yi separated with another space

(|Xi|, |Yi| ≤ 1000). The first letter will either be "L" or "M".

There is one empty line after each test case. You may assume that no real (absolute) coordinate

will be further than 30 000 in any direction from the picture starting point.

Output Specification

For each test case, print one line containing either "YES" if the two pictures are equivalent, or

"NO" if they differ.

Sample Input

2

L11

L11

1

L -2 -2

2

L11

L11

1

L33

5

L

1

0

L

1

0

L

0

5

L

0

-5

L

2

0

3

L

05

M

-2 -5

L

40

Output for Sample Input

YES

NO

YES