[Daimayuan] 碰撞2（C++，模拟）

在 $xOy$ 坐标系中有 $N$ 个人，第 $i$ 个人的位置是 (Xi,Yi)(X_i,Y_i)(Xi​,Yi​)，并且每个人的位置都不同。

我们有一个由 L 和 R 组成的长为 $N$ 的字符串 $S$，Si=S_i=Si​= R 代表第 $i$ 个人面向右，Si=S_i=Si​= L 代表第 $i$ 个人面向左。

现在所有人开始朝着他们各自面向的方向走，即面向右 $x$ 就增，面向左 $x$ 就减。

例如，当 (X1,Y1)=(2,3)(X_1,Y_1)=(2,3)(X1​,Y1​)=(2,3),(X2,Y2)=(1,1)(X_2,Y_2)=(1,1)(X2​,Y2​)=(1,1),(X3,Y3)=(4,1)(X_3,Y_3)=(4,1)(X3​,Y3​)=(4,1),$S=$ RRL 时，人们的移动如图。

我们把两个人对向行走到一个位置称为一次碰撞。请问如果人们可以无限走下去，会有人产生碰撞吗？

输入格式

第一行一个整数 $N$；

接下来 $N$ 行，每行两个整数 XiX_iXi​ 和 YiY_iYi​，表示第 $i$ 个人的位置；

最后一行是一个由 L 和 R 组成的长为 $N$ 的字符串 $S$。

输出格式

如果会有碰撞，输出 Yes，否则输出 No。

样例输入 1

3
2 3
1 1
4 1
RRL

样例输出 1

Yes

样例输入 2

2
1 1
2 1
RR

样例输出 2

No

样例输入 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≤N≤2×1052≤N≤2×10^52≤N≤2×105，0≤Xi≤1090≤X_i≤10^90≤Xi​≤109，0≤Yi≤1090≤Y_i≤10^90≤Yi​≤109。

解题思路

根据题意，我们很容易就能得出碰撞条件：

（1）同一行中，即$y$相同

（2）行走方向相反

（3）向右走的人在左边，向左走的人在右边

那么我们的思路形成了：

遍历每一行，找出每一行中的min{x∣x为向右走的人的横坐标}min\\{x|x为向右走的人的横坐标\\}min{x∣x为向右走的人的横坐标}和max{y∣y为向左走的人的横坐标}max\\{y|y为向左走的人的横坐标\\}max{y∣y为向左走的人的横坐标}

接下来的问题就是如何存储数据

显然，想要对应每一个$y$值开一个数组是不现实的

但是我们简单思考一下，发现也没必要为每一个$y$值开一个数组

采用sort算法，把相同$y$值的个体连在一起就可以了

最后，AC代码如下

#include <iostream>
#include <algorithm>
using namespace std;
const int max_n = 2e5;
const int max_x = 1e9;
const int max_y = 1e9;
const int NaN = 0x3F3F3F3F;int n;
struct person { int x, y, dirction; }persons[max_n + 1];int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> persons[i].x >> persons[i].y;}string str;cin >> str;for (int i = 0; i < n; i++) {if (str[i] == 'R') persons[i + 1].dirction = 0;else persons[i + 1].dirction = 1;}sort(persons + 1, persons + 1 + n, [](person p1, person p2) {return p1.y < p2.y;});int line = -1, l = NaN, r = -1;for (int i = 1; i <= n; i++) {if (persons[i].y == line) {if (persons[i].dirction) r = max(r, persons[i].x);else l = min(l, persons[i].x);}else {if (l < r) {cout << "Yes" << endl;return 0;}l = NaN; r = -1;line = persons[i].y;if (persons[i].dirction) r = max(r, persons[i].x);else l = min(l, persons[i].x);}}if (l < r) cout << "Yes" << endl;else cout << "No" << endl;return 0;
}