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 for_(i,a,b) for(int i=(a);i<(b);++i)
typedef pair< int, int > pii;

pii getRange(int w, int d, int x, int y, char f) {
	if (f == 'N') {
		int a = x - (d - y), b = (w - x) - (d - y);
		return pii(a, w - b);
	}
	
	if (f == 'E') {
		int a = (d - y) - (w - x), b = y - (w - x);
		return pii(w + a, w + d - b);
	}
	
	if (f == 'S') {
		int a = (w - x) - y, b = x - y;
		return pii(w + d + a, 2*w + d - b);
	}
	
	if (f == 'W') {
		int a = y - x, b = (d - y) - x;
		return pii(2*w + d + a, 2*w+2*d - b);
	}
	
	return pii(-1,-1);
}

int solve(int n, vector< vector< int > >& collision, vector< int >& order, int s) {
	int ret = 0;
	vector< bool > bad(n, false);
	for_(i,0,n) {
		int v = order[(s + i) % n];
		if (bad[v]) continue;
		++ret;
		for (int u : collision[v]) bad[u] = true;
	}
	return ret;
}

struct Rng {
	int id, L, R;
	Rng(int __id, pii p) : id(__id), L(p.first), R(p.second) {}
	bool operator < (const Rng& o) const { return R < o.R; }
};

int main() {
	int n, w, d;
	cin >> n >> w >> d;
	
	int UB = 2*w + 2*d;
	vector< Rng > vp;
	for_(i,0,n) {
		int x, y; char f;
		cin >> x >> y >> f;
		pii p = getRange(w, d, x, y, f);
		vp.push_back(Rng(i, p));
		vp.push_back(Rng(i, pii(p.first + UB, p.second + UB)));
	}
	
	sort(vp.begin(), vp.end());
	vector< int > order, vis(n, false);
	for (Rng r : vp) if (!vis[r.id]) order.push_back(r.id), vis[r.id] = true;
	
	vector< vector< int > > collision(n, vector< int >());
	for (Rng x : vp) for (Rng y : vp) {
		if (x.id == y.id) continue;
		if (x.R >= y.L && x.L <= y.R) collision[x.id].push_back(y.id);
	}
	
	cout << max(solve(n, collision, order, 0), max(solve(n, collision, order, 1), solve(n, collision, order, 2))) << endl;
}