Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <numeric>
#include <string>
#include <cstring>
#include <complex>
#include <cstdio>
#include <cstdlib>
using namespace std;

#define REP(i, n) for(int i=0;i<(int)n;i++)
#define REPS(i, n) for(int i=1;i<=(int)n;i++)
#define RREP(i, n) for(int i=n-1;i>=0;i--)
#define RREPS(i, n) for(int i=n;i>0;i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define pb push_back
#define eb emplace_back
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int T, n, w, h;
int m;
int place(int x, int y, int dx, int dy){
	int step = 10000000;
	if(dx > 0) step = min(step, w - x);
	if(dx < 0) step = min(step, x);
	if(dy > 0) step = min(step, h - y);
	if(dy < 0) step = min(step, y);
	x += dx * step;
	y += dy * step;
	if(y == 0) return x;
	if(x == w) return w + y;
	if(y == h) return 2*w+h - x;
	if(x == 0) return 2*w+2*h - y;
	assert(false);
}


int solve(vector<pii> rng){
	int ans = 1;
	int tail = rng[0].first - 1;
	int start = tail;
	for(auto it : rng){
		int s, t;
		tie(t, s) = it;
		if(s <= tail) continue;
		if(start + m < t) continue;
		ans ++;
		tail = t-1;
	}
	return ans;
}
int main(){
	cin >> n >> w >> h;
	m = 2*w+2*h;
	vector<pii> rng;
	REP(i, n){
		int x, y;
		char f;
		cin >> x >> y >> f;
		int s, t;
		if(f == 'E'){
			s = place(x, y, 1, -1);
			t = place(x, y, 1, 1) + 1;
		}
		if(f == 'N'){
			s = place(x, y, 1, 1);
			t = place(x, y, -1, 1) + 1;
		}
		if(f == 'W'){
			s = place(x, y, -1, 1);
			t = place(x, y, -1, -1) + 1;
		}
		if(f == 'S'){
			s = place(x, y, -1, -1);
			t = place(x, y, 1, -1) + 1;
		}
		if(t <= s) t += m;
		rng.eb(t, s);
	}
	int ans = n;
	REP(_, 2*n){
		sort(ALL(rng));
		ans = min(ans, solve(rng));
		rng[0].first += m;
		rng[0].second += m;
		rng.eb(rng[0]);
		rng.erase(rng.begin());
	}
	cout << ans << endl;
	return 0;
}