#P3487. [Poi2013]Maze
[Poi2013]Maze
Labirynt
题目描述
Bajtazar 读到一个希腊王子用毛线团战胜怪物的故事。故事的高潮发生在一座迷宫里,这让他迷上了画迷宫。
他的迷宫是画在方格纸上的简单多边形。每条边都平行于一条坐标轴,相邻两条边互相垂直。从某条边的内部选一个入口,沿边走一圈,始终用右手贴着墙壁,最后回到入口。每逢墙壁转向,左转记作 L,右转记作 P。
给定一串转向记录,判断是否存在对应的迷宫。如果存在,输出任意一个。入口可以选在任何一条边上,因此允许从对应记录的任意位置开始沿边走。
输入格式
输入一行字符串 ,只包含 L 和 P。设 。
输出格式
若无法构造,输出一行 NIE。
否则输出恰好 行,每行两个整数 ,表示第 个顶点。满足 。逆时针按边界顺序输出所有顶点,可以从任意顶点开始。最后一个顶点与第一个顶点相连。无需另行标出入口。
样例 #1
LLLLPPLL
0 0
2 0
2 2
-1 2
-1 -2
1 -2
1 -1
0 -1

数据范围
。原赛中, 的分数对应 的测试。
原赛提供了三项附加测试说明。第一项为 个 L,答案为 NIE。第二项长 ,是向左转的螺旋。第三项长 ,形状为阶梯。原比赛的输出可视化器可以绘制格式正确的迷宫。