Czech ACM Student Chapter
Czech Technical University in Prague
Charles University in Prague
Technical University of Ostrava
Slovak University of Technology
Pavol Jozef Saf´rik University in Koˇice
University of Zilina
Matej Bel University in Bansk´ Bystrica
University of West Bohemia
CTU Open Contest 2014
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.
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.
For each test case, print one line containing either "YES" if the two pictures are equivalent, or
"NO" if they differ.
L -2 -2
Output for Sample Input