QOJ.ac

QOJ

時間限制: 10.0 s 記憶體限制: 256 MB 總分: 100

#15988. 不变的图像

统计

信息隐藏(Steganography)是一种保护信息的特殊方法——与加密不同,它是将信息以某种方式隐藏起来。从历史上看,这是一种相当流行的方法,但如今它已被密码学(尤其是基于密钥的密码)所取代。然而,有时它仍在使用。数字信息隐藏技术之一是将一小部分信息隐藏在数字图像中。图像的修改非常微小,以至于人眼无法察觉,但信息(如文本信息)确实存在且可被计算机读取。你的任务是对比两幅图像并找出这些(可能很微小的)差异。

在本题中,我们将关注矢量图。你的程序将获得两幅图片,并需要判断它们是否包含相同的图像。从几何学上讲,即判断这两幅图片是否相似,这意味着它们是否可以通过平移、旋转和等比例缩放(但不包括镜像反射)相互转换。以下是两幅相似图片的示例。

两幅相似图片的示例

输入格式

输入文件包含多个测试用例,每个测试用例包含两幅矢量图。每幅图片由绘图仪(plotter)的一系列指令描述,每行一条指令。

每条指令以一个大写字母开头,后跟一个空格和两个由另一个空格分隔的整数坐标。字母为 “L”(画线)或 “M”(移动而不画线)。坐标指定了画线的目标位置或当前位置移动到的目标位置。坐标总是相对于前一条指令的终点位置给出(即相对坐标)。第一条指令是相对于某个(未指定的)起点给出的。

每幅图片的最后一条指令后面紧跟一行,包含字母 “E”(结束)和一个空行。最后一个测试用例后面会紧跟一行,包含字母 “Q”(退出)。

任何图片的指令数量在 $0$ 到 $1000$ 之间(含 $0$ 和 $1000$)。没有任何一条指令的两个坐标同时为零。所有(相对)坐标的绝对值最大为 $1000$。

输出格式

对于每个测试用例,输出一行,包含单词 “YES”(两幅图片相似)或 “NO”(两幅图片不相似)。

样例

输入样例 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

输出样例 1

YES
NO
YES

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.