Collision 2

题目描述

在 $xy$ 平面上有 $N$ 个人。第 $i$ 个人位于 $(X_i, Y_i)$。所有人的位置都不相同。 我们有一个长度为 $N$ 的字符串 $S$，由 $L$ 和 $R$ 组成。
如果 $S_i =$ $R$，第 $i$ 个人面向右；如果 $S_i =$ $L$，第 $i$ 个人面向左。所有人同时开始沿着他们面向的方向行走。这里，右和左分别对应正和负 $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$。

3
2 3
1 1
4 1
RRL

Yes

2
1 1
2 1
RR

No

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

Yes

提示

$2 \leq N \leq 2 \times 10^5$ $0 \leq X_i \leq 10^9$ $0 \leq Y_i \leq 10^9$ $(X_i, Y_i) \neq (X_j, Y_j)$ 如果 $i \neq j$。 所有 $X_i$ 和 $Y_i$ 都是整数。 $S$ 是一个长度为 $N$ 的由 $L$ 和 $R$ 组成的字符串。该输入对应问题描述中的示例。
如果所有人继续行走，第 2 号和第 3 号会发生碰撞。因此应当输出 $Yes$。
由于第 1 号和第 2 号朝相同方向行走，他们永远不会碰撞。

标签: AtCoder|abc243C

来源

AtCoder|abc243C