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;
typedef long long ll;

struct Seg{
	int l, r;
	bool operator < (const Seg& x) const{
		if(l != x.l) return l < x.l;
		return r > x.r;
	}
};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	int H, W, N;
	cin >> N >> W >> H;
	deque<Seg> deq;
	for(int i = 0; i < N; i++){
		int x, y;
		char c;
		cin >> x >> y >> c;
		int l, r;
		if(c == 'W') l = y - x, r = y + x;
		if(c == 'N') l = H + x - (H - y), r = H + x + (H - y);
		if(c == 'E') l = W + H + (H - y) - (W - x), r = W + H + (H - y) + (W - x);
		if(c == 'S') l = W + 2 * H + (W - x) - y, r = W + 2 * H + (W - x) + y;
		if(l < 0){
			l += 2 * (H + W);
			r += 2 * (H + W);
		}
		deq.push_back({ l, r });
	}
	sort(deq.begin(), deq.end());

	int ans = 1e9;
	for(int i = 0; i < N; i++){
		queue<Seg> q;
		for(int i = 0; i < N; i++){
			q.push(deq[i]);
		}

		int sum = 0;
		while(q.size()){
			Seg s = q.front();
			q.pop();
			int l = s.l, r = s.r;
			while(q.size()){
				int ll = q.front().l, rr = q.front().r;
				if(l <= ll && ll <= r){
					l = max(l, ll);
					r = min(r, rr);
					q.pop();
				}
				else break;
			}
			sum++;
		}
		ans = min(ans, sum);

		Seg s = deq.front();
		s.l += 2 * (H + W), s.r += 2 * (H + W);
		deq.pop_front();
		deq.push_back(s);
	}
	cout << ans << endl;
}