AT_abc243_c [ABC243C] Collision 2

题目描述

在 $xy$ 坐标平面上有 $N$ 个人。第 $i$ 个人位于 $(X_i, Y_i)$。所有人都在不同的位置。

有一个由 L 和 R 组成的长度为 $N$ 的字符串 $S$。
如果 $S_i =$ R，第 $i$ 个人就面朝右（$x$ 轴正方向）；如果 $S_i =$ L，就面朝左（$x$ 轴负方向）。所有人会以相同的速度同时开始行走。

例如，若 $(X_1, Y_1) = (2, 3)$，$(X_2, Y_2) = (1, 1)$，$(X_3, Y_3) = (4, 1)$，$S =$ RRL，则他们的移动如下图所示。

我们称，若两个人朝相反方向行走并在同一位置相遇，则发生了“碰撞”。请判断当所有人一直行走时，是否会发生碰撞。

输入格式

输入以如下格式从标准输入读入。

$N$
$X_1\ Y_1$
$X_2\ Y_2$
$\vdots$
$X_N\ Y_N$
$S$

输出格式

如果会发生碰撞，输出 Yes；否则输出 No。

输入输出样例 #1

输入 #1

3
2 3
1 1
4 1
RRL

输出 #1

Yes

输入输出样例 #2

输入 #2

2
1 1
2 1
RR

输出 #2

No

输入输出样例 #3

输入 #3

10
1 3
1 4
0 0
0 2
0 4
3 1
2 4
4 2
4 4
3 3
RLRRRLRLRR

输出 #3

Yes

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $0 \leq X_i \leq 10^9$
• $0 \leq Y_i \leq 10^9$
• 若 $i \neq j$，则 $(X_i, Y_i) \neq (X_j, Y_j)$。
• $X_i, Y_i$ 均为整数。
• $S$ 是只包含 L 和 R 的长度为 $N$ 的字符串。

样例解释 1

该输入与题目描述中的例子相同。所有人一直行走时，第 $2$ 个人和第 $3$ 个人会发生碰撞。因此输出 Yes。

样例解释 2

第 $1$ 个人和第 $2$ 个人朝同一方向行走，因此不会发生碰撞。

由 ChatGPT 4.1 翻译