题解：P9957 [USACO20DEC] Stuck in a Rut B

由于 \(x, y \leq 10^9\)，我们无法模拟每个时间段。因此，我们需要尝试判断两头牛何时会相交。

一个重要的观察是，牛不能后退，所以两头牛发生碰撞的唯一方式是 \(n[x] > e[x]\) 且 \(n[y] < e[y]\)。

可以按牛的起始坐标进行排序，然后模拟这些碰撞。

代码：

#include<bits/stdc++.h>
using namespace std;
bool flag_2;
int n;
struct s{//sheep
	int ans=INT_MAX;
	char dir;
	int x,y;
};
s ss[55];//sheeps
bool check(s,s);
void chuli(s&,s&);
bool check(s a,s b){//路径上是否有同一点
	if(a.dir==b.dir) return false;
	if(a.dir!='N') swap(a,b);
	if(a.x<=b.x) return false;
	if(b.y<=a.y) return false;
	return true;
}
void chuli(s &a,s &b){
	bool flag=false;
	if(a.dir!='N'){
		swap(a,b);
		flag=true;
	}
	int x=a.x;
	int y=b.y;
	int dis_a=abs(y-a.y);
	int dis_b=abs(x-b.x);
	if(a.ans<dis_a&&b.ans==dis_b) b.ans=INT_MAX,flag_2=true;//如果A判断为被B撞且B在撞A之前已经停下了
	if(b.ans<dis_b&&a.ans==dis_a) a.ans=INT_MAX,flag_2=true;
	if(dis_a<dis_b&&a.ans>=dis_a&&b.ans>dis_b)
		b.ans=dis_b,flag_2=true;
	if(dis_a>dis_b&&b.ans>=dis_b&&a.ans>dis_a)
		a.ans=dis_a,flag_2=true;
	if(flag) swap(a,b);
	return;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>ss[i].dir>>ss[i].x>>ss[i].y;
	while(true){
		flag_2=false;
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				if(check(ss[i],ss[j]))
					chuli(ss[i],ss[j]);
			}
		}
		if(!flag_2) break;
	}
	for(int i=1;i<=n;i++)
		if(ss[i].ans!=INT_MAX) cout<<ss[i].ans<<'\n';
		else puts("Infinity");
	return 0;
}