Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef pair<int,int> P;
int N,W,H,L;
vector<int> es;
vector<P> vc,now;
int mn[2010];
int A;
int inf=1e8;
void solve(int e){
//	show(e);
	now.clear();
	for(P p_:vc){
		P p=p_;
		while(p.fs<e) p.fs+=L;
		while(p.fs>p.sc) p.sc+=L;
		p.fs-=e,p.sc-=e;
		if(p.fs==0||(p.fs<=L&&L<=p.sc)) continue;
		now.pb(p);
	}
	vector<int> ash;
	ash.pb(0);
	for(P p:now) ash.pb(p.fs),ash.pb(p.sc);
	sort(all(ash));
	ash.erase(unique(all(ash)),ash.end());
	int M=ash.size();
	for(P& p:now) p.fs=lower_bound(all(ash),p.fs)-ash.begin(),p.sc=lower_bound(all(ash),p.sc)-ash.begin();
//	show(M);
//	for(P p:now) cout<<p.fs<<" "<<p.sc<<endl;
	rep(i,M+1) mn[i]=inf;
	for(P p:now) chmin(mn[p.fs],p.sc);
	for(int i=M-2;i>=0;i--) chmin(mn[i],mn[i+1]);
	int x=0,ans=0;
	while(x<inf){
		x=mn[x+1];
		ans++;
	}
//	show(ans);
	chmin(A,ans);
}
int main(){
	cin>>N>>W>>H;
	L=2*(W+H);
	rep(i,N){
		int x,y;
		char c;
		cin>>x>>y>>c;
		int t[4]={x+y+H,y-x+2*W+H,-y-x+3*H+2*W,x-y+H};
		rep(i,4) t[i]%=L;
		if(c=='E') vc.pb(P(t[0],t[1]));
		if(c=='N') vc.pb(P(t[1],t[2]));
		if(c=='W') vc.pb(P(t[2],t[3]));
		if(c=='S') vc.pb(P(t[3],t[0]));
	}
	rep(i,N) es.pb(vc[i].fs),es.pb(vc[i].sc);
//	rep(i,N) printf("(%d,%d)\n",vc[i].fs,vc[i].sc);
	A=inf;
	for(int e:es) solve(e);
//	solve(14);
	cout<<A<<endl;
}