Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

#define dump(...) cout<<"# "<<#__VA_ARGS__<<'='<<(__VA_ARGS__)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}

template<typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
	print_tuple<Cdr...>(os,t);
	os<<(sizeof...(Cdr)?",":"")<<get<sizeof...(Cdr)>(t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
	print_tuple<Args...>(os<<'(',t);
	return os<<')';
}

template<typename Ch,typename Tr,typename C>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;

typedef tuple<int,int,int> tiii;

int main()
{
	for(int n,w,h;cin>>n>>w>>h && n|w|h;){
		int p=2*(w+h);
		vector<pii> rs;
		rep(i,n){
			int x,y; string d; cin>>x>>y>>d;
			if(d=="N"){
				int l=x-(h-y),r=x+(h-y);
				rs.emplace_back(l,r);
			}
			if(d=="E"){
				int b=y-(w-x),t=y+(w-x);
				rs.emplace_back(w+(h-t),w+(h-b));
			}
			if(d=="S"){
				int l=x-y,r=x+y;
				rs.emplace_back(w+h+(w-r),w+h+(w-l));
			}
			if(d=="W"){
				int b=y-x,t=y+x;
				rs.emplace_back(w+h+w+b,w+h+w+t);
			}
		}
		rep(i,n) if(rs[i].first<0){
			rs[i].first+=p;
			rs[i].second+=p;
		}
		
		int res=INF;
		rep(i,n){
			priority_queue<tiii,vector<tiii>,greater<tiii>> pq;
			rep(j,n){
				if(rs[j].first>=rs[i].first){
					pq.emplace(rs[j].first,0,j);
					pq.emplace(rs[j].second,1,j);
				}
				else{
					pq.emplace(rs[j].first+p,0,j);
					pq.emplace(rs[j].second+p,1,j);
				}
			}
			set<int> require;
			int cnt=0;
			while(pq.size()){
				int l,s,j; tie(l,s,j)=pq.top(); pq.pop();
				if(s==0){ // open
					require.insert(j);
				}
				else{ // close
					if(require.count(j)){
						cnt++;
						require.clear();
					}
				}
			}
			res=min(res,cnt);
		}
		cout<<res<<endl;
	}
}