P13470 [GCJ 2008 #3] How Big Are the Pockets?

Polygonovich 教授是 Flatland 的一位诚实市民，他喜欢在平面上的整数点之间进行随机行走。他每天早晨从原点出发，面朝北方。他有三种行动方式： - 'F'：向前移动一个单位长度。 - 'L'：向左转 $90$ 度。 - 'R'：向右转 $90$ 度。 一天结束时（是的，他走了很久！），他会回到原点。他在行走过程中，除了原点外，绝不会两次经过同一个点，因此他的路径围成了一个多边形。下图中，多边形的内部被涂成了蓝色（暂时忽略 $x$、$y$、$z$ 和 $w$ 这几个点，稍后会解释）：  注意，只要 Polygonovich 教授转弯次数超过 $4$ 次，这个多边形就不是凸多边形，因此会出现“口袋”区域。 **注意！** 为了增加难度，我们对“口袋”的定义可能与你以往听说的不同。 下图中灰色区域表示多边形的口袋。  形式化地说，一个点 $p$ 被认为在口袋中，当且仅当它不在多边形内部，并且满足以下两个条件之一： - $p$ 的正东和正西方向上都存在边界点；或者 - $p$ 的正北和正南方向上都存在边界点。 边界点指的是 Polygonovich 先生在行走过程中经过的所有点（包括所有点，不仅限于整数坐标点）。 再看上面的第一张图。点 $x$ 满足第一个条件；$y$ 同时满足两个条件；$z$ 满足第二个条件。这三个点都在口袋中。点 $w$ 不在口袋中。 给定 Polygonovich 教授的行走路径，请你计算所有口袋区域的总面积。

输入的第一行是测试用例数 $N$。接下来有 $N$ 组测试数据。 每组测试数据描述了 Polygonovich 教授的一次行走。每组数据以一个整数 $L$ 开头。接下来是 $L$ 个 "S T" 对，其中 $S$ 是仅由 'L'、'R'、'F' 组成的字符串，$T$ 是一个整数，表示 $S$ 重复的次数。 换句话说，每组测试数据的输入格式如下： $S_1$ $T_1$ $S_2$ $T_2$ ... $S_L$ $T_L$ 实际的行动序列是 $T_1$ 个 $S_1$，接着 $T_2$ 个 $S_2$，依此类推，拼接而成。 同一组测试数据中的 "S T" 对可能不会全部在同一行，但字符串 $S$ 不会被拆分到多行。下面的第二个样例演示了这一点。

对于每组测试数据，输出一行，格式为 "Case #$X$: $Y$"，其中 $X$ 是测试用例编号（从 $1$ 开始），$Y$ 是所有口袋区域的总面积。

**样例解释** 下图展示了两个样例测试数据的情况。  **数据范围** - $1 \leqslant N \leqslant 100$ - $1 \leqslant T$（上界见下述“小数据集”和“大数据集”说明） - 输入拼接后的路径中不会出现连续的方向变化（即不会有 'LL'、'RR'、'LR' 或 'RL'），并且路径中至少包含一个 'F'。 - 路径不会自交，除了起点和终点重合，并且最终会回到原点。 **小数据集（5 分，测试点 1 - 可见）** - $1 \leqslant L \leqslant 100$ - 每个字符串 $S$ 的长度为 $1$ 到 $16$。 - 教授不会经过绝对值大于 $100$ 的点。 **大数据集（10 分，测试点 2 - 隐藏）** - $1 \leqslant L \leqslant 1000$ - 每个字符串 $S$ 的长度为 $1$ 到 $32$。 - 教授不会经过绝对值大于 $3000$ 的点。 由 ChatGPT 4.1 翻译