[Daimayuan] 碰撞2（C++，模拟）-Toy模板网

这篇具有很好参考价值的文章主要介绍了[Daimayuan] 碰撞2（C++，模拟）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

在 $x O y$ 坐标系中有 $N$ 个人，第 $i$ 个人的位置是 $X_i,Y_i)$ ，并且每个人的位置都不同。

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

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

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

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

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

输入格式

第一行一个整数 $N$ ；

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

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

输出格式

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

样例输入 1

样例输出 1

Yes

样例输入 2

样例输出 2

No

样例输入 3

样例输出 3

Yes

数据规模

所有数据保证 $2≤N≤2×10^5$ ， $0≤X_i≤10^9$ ， $0≤Y_i≤10^9$ 。

解题思路

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

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

（2）行走方向相反

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

那么我们的思路形成了：

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

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

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

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

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

最后，AC代码如下文章来源地址https://www.toymoban.com/news/detail-408346.html

#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;
}