P3559 [POI 2013] LAB-Maze

注意：在比赛期间，你可以询问关于此问题任意三个提交的得分情况。 拜特萨最近读了一个有趣的故事。 故事的主人公是一位希腊王子，他用一根毛线击败了怪物，或诸如此类的情节。 但故事中另一点让拜特萨着迷的是：高潮部分发生在一个迷宫中。 从那时起，拜特萨就对迷宫产生了浓厚的兴趣。 拜特萨在方格纸上绘制迷宫草图。 每个草图是一个多边形（代表迷宫的墙壁），其边平行于纸张的边缘（即笛卡尔坐标系的坐标轴），且每两条相邻边相互垂直。 拜特萨发现，如果将入口放置在迷宫的某条边（**不能是顶点**）上，那么通过始终将右手放在墙上行走，可以遍历整个迷宫并返回入口。 此外，在迷宫遍历过程中，我们可以记录所采取的转弯方向。 当从一面墙移动到另一面墙时，如果左转，我们记下字母 `L`；如果右转，则记下字母 `P`。 拜特萨想知道，对于给定的由字母 `L` 和 `P` 组成的字符串，是否存在一个迷宫，其遍历过程恰好生成该字符串，如果是，则输出这个迷宫。

标准输入的第一行给出一个由字母 `L` 和 `P` 组成的字符串 $S$（$1 \leq |S| \leq 10^5$），描述了在迷宫遍历过程中连续转弯的序列。 在占总分 $50\%$ 的测试用例中，额外满足约束 $|S| \leq 1000$。

如果没有迷宫与输入的描述相对应，则在标准输出上打印单词 `NIE`（波兰语中的“否”）。 否则，应恰好输出 $|S|$ 行，指定任意一个与输入一致的迷宫，格式如下： 第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（用单个空格分隔），表示迷宫草图第 $i$ 个顶点的坐标。 顶点需按多边形外围**逆时针**顺序输出；可以选择任意一个顶点作为第一个顶点，且无需指明入口的位置。

翻译由 Deepseek-V3 完成，并进行了微调。