#P3487. [Poi2013]Maze

    ID: 2700 传统题 1000ms 128MiB 尝试: 24 已通过: 8 难度: 9 上传者: 标签>难度分类提高+/省选-构造与建模不变量分析逆向还原操作数据结构链表队列模拟与实现技巧增量维护排序与序列处理离散化CF2600

[Poi2013]Maze

Labirynt

题目描述

Bajtazar 读到一个希腊王子用毛线团战胜怪物的故事。故事的高潮发生在一座迷宫里,这让他迷上了画迷宫。

他的迷宫是画在方格纸上的简单多边形。每条边都平行于一条坐标轴,相邻两条边互相垂直。从某条边的内部选一个入口,沿边走一圈,始终用右手贴着墙壁,最后回到入口。每逢墙壁转向,左转记作 L,右转记作 P。

给定一串转向记录,判断是否存在对应的迷宫。如果存在,输出任意一个。入口可以选在任何一条边上,因此允许从对应记录的任意位置开始沿边走。

输入格式

输入一行字符串 SS,只包含 L 和 P。设 n=∣S∣n=|S|。

输出格式

若无法构造,输出一行 NIE。

否则输出恰好 nn 行,每行两个整数 xi,yix_i,y_i,表示第 ii 个顶点。满足 −109≤xi,yi≤109-10^9\le x_i,y_i\le 10^9。逆时针按边界顺序输出所有顶点,可以从任意顶点开始。最后一个顶点与第一个顶点相连。无需另行标出入口。

样例 #1

LLLLPPLL
0 0
2 0
2 2
-1 2
-1 -2
1 -2
1 -1
0 -1

样例给出的迷宫外轮廓

数据范围

1≤n≤1051\le n\le 10^5。原赛中,50%50\% 的分数对应 n≤2500n\le 2500 的测试。

原赛提供了三项附加测试说明。第一项为 1212 个 L,答案为 NIE。第二项长 100100,是向左转的螺旋。第三项长 100 000100\,000,形状为阶梯。原比赛的输出可视化器可以绘制格式正确的迷宫。