Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <tuple>

using namespace std;
typedef pair<int, int> pii;
static const int INF = 1000000000;

int main(){
	ios_base::sync_with_stdio(false);
	int n, w, h;
	cin >> n >> w >> h;
	vector<pii> ranges;
	for(int i = 0; i < n; ++i){
		int x, y;
		string f;
		cin >> x >> y >> f;
		const int hw2 = h + w + h + w;
		const int lu = y + x;
		const int ru = h + x + (h - y);
		const int rd = h + w + (h - y) + (w - x);
		const int ld = h + w + h + (w - x) + y;
		int lo = 0, hi = 0;
		if(f[0] == 'N'){
			lo = lu; hi = ru;
		}else if(f[0] == 'E'){
			lo = ru; hi = rd;
		}else if(f[0] == 'S'){
			lo = rd; hi = ld;
		}else if(f[0] == 'W'){
			lo = ld; hi = lu + hw2;
		}
		if(lo >= hw2){
			lo -= hw2;
			hi -= hw2;
		}
		ranges.emplace_back(lo, hi);
		ranges.emplace_back(lo + hw2, hi + hw2);
	}
	sort(ranges.begin(), ranges.end());
	int answer = INF;
	for(int i = 0; i < n; ++i){
		const int hw2 = (h + w) * 2;
		vector<pii> r(ranges.begin() + i, ranges.begin() + i + n);
		sort(r.begin(), r.end(), [](const pii &a, const pii &b){
			return (a.second == b.second) ? (a.first < b.first) : (a.second < b.second);
		});
		int count = 1, last = r[0].second;
		for(int j = 0; j < n; ++j){
			if(r[j].first <= last){ continue; }
			if(r[j].second >= r[0].second + hw2){ continue; }
			++count;
			last = r[j].second;
		}
		answer = min(answer, count);
	}
	cout << answer << endl;
	return 0;
}