Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include <iostream>
#include <string>
#include <cassert>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

const int MN = 1010;
int n, ro;
int l[MN], r[MN];


int solve() {
//	cout << n << " " << ro << endl;
//	for (int i = 0; i < n; i++) {
//		cout << l[i] << " " << r[i] << endl;
//	}

	for (int i = 0; i < n; i++) {
		if (r[i] < l[i]) r[i] += ro;
	}
	int mi = 100000;
	for (int i = 0; i < n; i++) {
		vector<P> v;
		for (int j = 0; j < n; j++) {
			if (l[j] <= l[i] && l[i] < r[j]) continue;
			if (l[j] <= l[i]+ro && l[i]+ro < r[j]) continue;
			if (l[i] < l[j]) {
				v.push_back(P(l[j], r[j]));
			} else {
				v.push_back(P(l[j]+ro, r[j]+ro));
			}
		}

		sort(v.begin(), v.end(), [&](const P &l, const P &r){
			if (l.second != r.second) return l.second < r.second;
			return l.first < r.first;
		});

		int m = (int)v.size();
		int re = 1;
		int ba = l[i];
		for (int j = 0; j < m; j++) {
			if (ba < v[j].first) {
				re++;
				ba = v[j].second-1;
			}
		}
//		printf("%d %d %d %d %d\n", i, m, re, v[0].first, v[0].second);
		mi = min(mi, re);
	}
	return mi;
}

int main() {
	int w, h;
	cin >> n >> w >> h;
	ro = 2*(h+w);
	for (int i = 0; i < n; i++) {
		int x, y; char c;
		cin >> x >> y; cin >> c; y = h-y;
		int di[4];
		if (y + (w-x) < h) {
			di[0] = w+y+(w-x);
		} else {
			di[0] = w+h+w-(x+(h-y));
		}

		if (x - (h-y) > 0) {
			di[1] = w+h+w-(x-(h-y));
		} else {
			di[1] = w+h+w+h-(y+x);
		}

		if (y - x > 0) {
			di[2] = w+h+w+h-(y-x);
		} else {
			di[2] = x-y;
		}

		if (x + y < w) {
			di[3] = x+y;
		} else {
			di[3] = w+y-(w-x);
		}
//		cerr << di[0] << " " << di[1] << " " << di[2] << " " << di[3] << endl;
		switch (c) {
		case 'E':
			l[i] = di[3];
			r[i] = di[0];
			break;
		case 'S':
			l[i] = di[0];
			r[i] = di[1];
			break;
		case 'W':
			l[i] = di[1];
			r[i] = di[2];
			break;
		case 'N':
			l[i] = di[2];
			r[i] = di[3];
			break;
		default:
			assert(false);
		}
		r[i]++;
	}
	cout << solve() << endl;
	return 0;
}