Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
	int n, w, d;
	while(cin >> n >> w >> d){
		vector< pair<int, int> > vp(n);
		for(int i=0;i<n;i++){
			int x, y; char f;
			cin >> x >> y >> f;
			int a, b;
			if(f == 'S'){
				a = x;
				b = y;
			} else if(f == 'E'){
				a = w+y;
				b = w-x;
			} else if(f == 'N') {
				a = w+d+w-x;
				b = d-y;
			} else if(f == 'W'){
				a = 2*w+d+d-y;
				b = x;
			}
			vp[i].first = (a-b+2*(w+d))%(2*(w+d));
			vp[i].second = (a+b)%(2*(w+d));
		}
		sort(vp.begin(),
				vp.end(),
				[](const pair<int, int>& a, const pair<int, int>& b){
					return a.second == b.second ? a.first < b.first : a.second < b.second;
				}
			);
		int res = n;
		for(int i=0;i<n;i++){
			int cnt = 1, pos = vp[i].second;
			for(int j=1;j<n;j++){
				pair<int, int> pr = vp[(i+j)%n];
				if(pr.first < pr.second ? (pr.first <= pos && pos <= pr.second) : (pos <= pr.second || pr.first <= pos)) continue;
				pos = pr.second;
				++cnt;
			}
			res = min(res, cnt);
		}
		cout << res << endl;
	}
}