QOJ.ac

QOJ

Límite de tiempo: 6 s Límite de memoria: 2048 MB Puntuación total: 100

#10464. 仿射混乱

Estadísticas

Tess L. Ation 上周在演示她的绘图软件测试版时遇到了一个小麻烦。屏幕上有一个优雅的演示设计,展示了她程序的所有功能;她花了数小时才完成它。就在她做最后润色时,一群潜在的投资者走进房间观看演示。

演示进行得很顺利。快结束时,Tess 点击了一个控制面板按钮,并告诉观众:“这是‘网格对齐’(snap to grid)控件。它强制控制点(例如顶点)跳转到最近的网格点。来,我演示给你们看。”她随后在屏幕上放置了三个鲜红色的点。每一个点都出现在她点击位置最近的网格点上。(“幸运的是,我演示设计中的所有控制点都已经位于整数坐标上了。但我得记得在保存图表前删除这三个红点,”她心想。)“现在我到隔壁房间去,给你们留出空间讨论这个系统,并仔细看看屏幕,但请不要触碰任何东西,因为我还没保存那个文件。”

几分钟后,这群人加入了 Tess。其中一位访客走到 Tess 面前说:“希望你不介意,但我自己想试一下。别担心,我只是稍微玩了一下 $x$ 轴缩放和 $y$ 轴缩放控件。”下一个人说:“如果这造成了问题我很抱歉,但我真的很想感受一下显示速度,所以我只是玩了一下平移工具。”第三个人说:“我忍不住做了一个小测试:我旋转了图像,这样我就可以看到所有顶点在旋转后都对齐到了最近的网格点。”

玩旋转工具的人记得他是第一个操作的,但另外两人记不清他们的顺序了。这三个人只记得关于改动的一些细节。$x$ 轴和 $y$ 轴的缩放因子是(可能是负的)非零整数;缩放中心是原点 $(0, 0)$。$x$ 轴和 $y$ 轴的平移量是整数。旋转由一个位于以原点为中心的边长为 20 的正方形周界上的整数坐标点 $(x, y)$ 指定(因此,$-10 \le x, y \le 10$,且 $x$ 或 $y$ 或两者之中的绝对值为 10)。该工具绕原点旋转绘图,使得正 $x$ 轴随后通过点 $(x, y)$。对齐操作发生在旋转之后(坐标小数部分为 0.5 的情况向远离零的方向舍入)。

他们离开后,Tess 看着她的设计——它完全变了!她还没有实现“撤销”功能,也没有在演示前保存图表。然而,那三个相同的红点还在那里(当然,被转换到了其他整数网格位置),Tess 还记得她最初放置它们时的整数坐标。显然,其他人可能在没告诉她的情况下改动了绘图,但她可以编写一个程序来看看是否有可能重构这一系列改动。你也可以吗?

输入格式

输入包含多个测试用例。每个测试用例包含六对整数 $x_i$ 和 $y_i$($-500 \le x_i, y_i \le 500$,对于 $1 \le i \le 6$),每行输入三对。前三对代表三个红点的初始位置。后三对代表三个红点的最终位置。每组三对点的索引并不重要:例如,$(x_1, y_1)$ 可能映射到 $(x_4, y_4)$、$(x_5, y_5)$ 或 $(x_6, y_6)$ 中的任意一个。

最后一个测试用例后跟有一行六个零。

输出格式

对于每个测试用例,显示其用例编号,后跟以下三条消息之一:

  • “equivalent solutions”:表示存在一个或多个有效的变换,且所有这些变换对整个绘图产生相同的影响(无论整个绘图看起来是什么样)。
  • “inconsistent solutions”:表示存在多个有效的变换,但通常并非所有变换都以相同的方式映射整个绘图(某些绘图被两个有效的变换映射为不同的结果)。
  • “no solution”:表示上述两种情况均不成立。

有效的变换是旋转、平移和缩放(或旋转、缩放和平移)的组合,它满足上述限制,并将初始红点集映射到最终红点集(占据所有三个最终位置)。

请遵循样例输出的格式。

样例

样例输入 1

3 0 4 0 1 4
-2 -4 -1 3 3 -4
0 1 1 1 2 1
1 2 2 2 3 2
1 0 2 0 3 0
3 3 1 1 2 2
1 0 2 0 3 0
3 2 1 1 2 2
2 3 0 6 1 2
2 3 0 6 1 2
0 0 0 0 0 0

样例输出 1

Case 1: equivalent solutions
Case 2: inconsistent solutions
Case 3: no solution
Case 4: inconsistent solutions
Case 5: equivalent solutions

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.