洛谷
题目要求找到哪些没有撞的。
考虑如何计算两个战舰是否会相撞。
如果两个方向分别向南北方向那么需要满足 \(x\) 坐标相等。
两个相遇时消耗的时间为两个的 \(y\) 坐标差值的一半（简单的相遇问题）。
东西方向同理可得。
然后考虑如果一个向北，一个向东，那么怎么判断是否会相遇。
我们先假设相撞的点为 \((x,y)\)，经过的时间为 \(t\)。
那么向北原本处于 \((x,y+t)\)，向东的原本处于 \((x-t,y)\)。
那么不难发现，我们需要保证这两个点的横坐标纵坐标差相等，并且方向要正确。
移项发现需要满足 \(y-x\) 的值相等时才有机会相撞。
其它的也用类似的方法推理即可。
那么我们把所有相撞方式分为 \(6\) 种，然后把有机会相撞的都给塞到一个 set 或者链表中。
按照横坐标或者纵坐标的值排序，显然相邻的两个更快相撞，并且如果两个无法相撞，那么两个可以看作两个需要反方向移动才能撞到，那么自然不用考虑越过这两个的点相撞。
判断能否相撞有直接枚举所有情况判断的笨方法，但实际上也可以改一下时间计算方法，如果计算出是负数或者方向相等则不会相撞，这样大概可以简化代码。
那么我们判断每个相邻的能否相撞，如果是，那么就加入一个小根堆中，每次把最小的取出来，进行修改即可。
注意多个撞到一起的情况也要考虑。
代码具体实现看代码和注释。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){char c=getchar();int x=0;bool f=0;while(c>'9'||c<'0'){if(c=='-')f=1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();if(f)return -x;return x;
}
int n,x[200005],y[200005],d[200005],vis[200005],id[6];
char op[3];
map<int,int> mp[6];
struct P{int v,x;bool friend operator<(P a,P b){return a.v<b.v;}P(int a,int b){v=a,x=b;}
};
set<P> s[6][200005];
void add(int op,int x,int v,int p){//加入set if(!mp[op][x])mp[op][x]=++id[op];s[op][mp[op][x]].insert({v,p});
}
void solve(int p,int x,int y,char op){if(op=='N'){d[p]=0;add(0,x,y,p),add(2,y-x,x,p),add(3,y+x,x,p);}if(op=='S'){d[p]=1;add(0,x,y,p),add(4,y+x,x,p),add(5,y-x,x,p);}if(op=='E'){d[p]=2;add(1,y,x,p),add(2,y-x,x,p),add(4,y+x,x,p);}if(op=='W'){d[p]=3;add(1,y,x,p),add(3,y+x,x,p),add(5,y-x,x,p);}
}
struct Q{int dis;P x,y;bool friend operator<(Q a,Q b){return a.dis>b.dis;}
};
priority_queue<Q> q;
int calc(int a,int b){//求时间 if(x[a]==x[b])return abs(y[a]-y[b])+1>>1;if(y[a]==y[b])return abs(x[a]-x[b])+1>>1;return abs(x[a]-x[b]);
}
bool check(int a,int b){//判断同一组中是否可以相撞（写的好像比较复杂，但也很无脑） if(d[a]==d[b])return false;if(d[a]==0&&d[b]==1&&y[a]>y[b])return true;if(d[a]==0&&d[b]==2&&y[a]>y[b])return true;if(d[a]==0&&d[b]==3&&y[a]>y[b])return true;if(d[a]==1&&d[b]==2&&y[a]<y[b])return true;if(d[a]==1&&d[b]==3&&y[a]<y[b])return true;if(d[a]==2&&d[b]==3&&x[a]<x[b])return true;swap(a,b);if(d[a]==0&&d[b]==1&&y[a]>y[b])return true;if(d[a]==0&&d[b]==2&&y[a]>y[b])return true;if(d[a]==0&&d[b]==3&&y[a]>y[b])return true;if(d[a]==1&&d[b]==2&&y[a]<y[b])return true;if(d[a]==1&&d[b]==3&&y[a]<y[b])return true;if(d[a]==2&&d[b]==3&&x[a]<x[b])return true;return false;
}
void solve2(int p){for(int j=1;j<=id[p];j++){int la=0;P tmp={0,0};for(P u:s[p][j]){if(la){if(check(la,u.x))q.push({calc(la,u.x),u,tmp});}la=u.x;tmp=u;}}
}
void del(int p,int w,P x){//删除并且把隔开的加入 w=mp[p][w];auto it=s[p][w].find(x);if(it==s[p][w].end())return;auto it2=it;it2++;if(it!=s[p][w].begin()&&it2!=s[p][w].end()){it--;if(check(it->x,it2->x))q.push({calc(it->x,it2->x),*it,*it2});}s[p][w].erase(x);
}
void Del(int p){if(d[p]==0)del(0,x[p],{y[p],p}),del(2,y[p]-x[p],{x[p],p}),del(3,y[p]+x[p],{x[p],p});if(d[p]==1)del(0,x[p],{y[p],p}),del(4,y[p]+x[p],{x[p],p}),del(5,y[p]-x[p],{x[p],p});if(d[p]==2)del(1,y[p],{x[p],p}),del(2,y[p]-x[p],{x[p],p}),del(4,y[p]+x[p],{x[p],p});if(d[p]==3)del(1,y[p],{x[p],p}),del(3,y[p]+x[p],{x[p],p}),del(5,y[p]-x[p],{x[p],p});
}
signed main(){n=read();for(int i=1;i<=n;i++){x[i]=read(),y[i]=read();scanf("%s",op);solve(i,x[i],y[i],op[0]);//加入对应的组 }for(int i=0;i<6;i++)solve2(i);//把相邻值加入小根堆 while(!q.empty()){Q u=q.top();q.pop();int x=u.x.x,y=u.y.x;if(vis[x]&&vis[x]<u.dis||vis[y]&&vis[y]<u.dis)continue;vis[x]=vis[y]=u.dis;Del(x),Del(y); }for(int i=1;i<=n;i++)if(!vis[i])printf("%lld\n",i);return 0;
}
/*
0 N S x
1 E W y
2 N E y-x
3 N W y+x
4 S E y+x
5 S W y-x
全部按照权值丢进set
计算方向不同的相邻船需要多少时间
丢进优先队列跑
然后开始赤石
*/