Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
//1????????????????£??????£?¶?????????????????????£????????????
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, w, h;
int x, y; char f;
int l[1000], r[1000];	//[l, r]

int toId(int px, int py) {
	if (py == 0) return px;
	if (px == w) return w + py;
	if (py == h) return w + h + (w - px);
	return 2 * w + h + (h - py);
}

int lay(int id, int x, int y) {
	int dist;
	int dx[4] = {1, -1, -1, 1};
	int dy[4] = {1, 1, -1, -1};
	
	if (dx[id] == 1) dist = w - x; else dist = x;
	if (dy[id] == 1) dist = min(dist, h - y); else dist = min(dist, y);
	
	int px = x + dist * dx[id];
	int py = y + dist * dy[id];
	return toId(px, py);
}

int main() {
	int i, j;
	
	cin >> n >> w >> h;
	for (i = 0; i < n; i++) {
		cin >> x >> y >> f;
		
		if (f == 'N') {
			l[i] = lay(1, x, y);
			r[i] = lay(0, x, y);
		}
		if (f == 'E') {
			l[i] = lay(0, x, y);
			r[i] = lay(3, x, y);
		}
		if (f == 'S') {
			l[i] = lay(3, x, y);
			r[i] = lay(2, x, y);
		}
		if (f == 'W') {
			l[i] = lay(2, x, y);
			r[i] = lay(1, x, y);
		}
		swap(l[i], r[i]);	//???????¨???????????????????????????????????????§, [???->?£?, ???->?£?]??¨????????????????????????
		if (r[i] < l[i]) {
			r[i] += 2 * w + 2 * h;
		}
	}
	
	typedef pair<int, int> P;
	P p[1000];
	for (i = 0; i < n; i++) p[i] = P(l[i], r[i]);
	sort(p, p + n);
	
	int ans = 114514;
	for (i = 0; i < n; i++) {
		int rMin = p[i].second;
		int ret = 0;
		for (j = 1; j < n; j++) {
			int pl;
			
			if (i + j < n) {
				pl = p[i + j].first;
			}
			else {
				pl = p[i + j - n].first + 2 * w + 2 * h;
			}
			
			if (pl > rMin) {
				ret++;
				rMin = 11451419;
			}
			rMin = min(rMin, p[(i + j) % n].second + (i + j >= n) * (2 * w + 2 * h));
		}
		ret++;
		ans = min(ans, ret);
	}
	cout << ans << endl;
	return 0;
}