Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;

#define rep(i,n) for(int i=0; i<n; i++)
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> pii;

int n, w, h;

int ru(int x, int y) {
	pii p1(x+h-y, h);
	pii p2(w, y+w-x);
	if(abs(p1.fi-x)+abs(p1.se-y) < abs(p2.fi-x)+abs(p2.se-y)) {
		return h+p1.fi;
	} else {
		return h*2 + w - p2.se;
	}
}

int rd(int x, int y) {
	pii p1(w, y-(w-x));
	pii p2(x+y, 0);
	if(abs(p1.fi-x)+abs(p1.se-y) < abs(p2.fi-x)+abs(p2.se-y)) {
		return w+h*2-p1.se;
	} else {
		return w*2 + h*2 - p2.fi;
	}
}

int lu(int x, int y) {
	pii p1(0, y+x);
	pii p2(x-(h-y), h);
	if(abs(p1.fi-x)+abs(p1.se-y) < abs(p2.fi-x)+abs(p2.se-y)) {
		return p1.se;
	} else {
		return h + p2.fi;
	}
}

int ld(int x, int y) {
	pii p1(0, y-x);
	pii p2(x-y, 0);
	if(abs(p1.fi-x)+abs(p1.se-y) < abs(p2.fi-x)+abs(p2.se-y)) {
		return p1.se;
	} else {
		return w*2 + h*2 - p2.fi;
	}
}

bool sortBySecond(const pii& lhs, const pii& rhs) {
	if( lhs.se == rhs.se ) {
		return lhs.fi < rhs.fi;
	}
	return lhs.se < rhs.se;
}

int main() {
	cin >> n >> w >> h;
	vector<pii> vp;
	rep(i, n) {
		int x, y;
		char f;
		cin >> x >> y >> f;
		if(f=='E') vp.push_back( pii(ru(x,y), rd(x,y)) );
		if(f=='W') vp.push_back( pii(ld(x,y), lu(x,y)) );
		if(f=='N') vp.push_back( pii(lu(x,y), ru(x,y)) );
		if(f=='S') vp.push_back( pii(rd(x,y), ld(x,y)) );
		if(vp[i].fi > vp[i].se) {
			vp[i].se += w*2 + h*2;
		}
	}

	int res = 10000000;
	for(int s=0; s<n; s++) {
		sort(vp.begin(), vp.end(), sortBySecond);
		int cnt = 1;
		int pos = vp[0].se;
		for(int i=1; i<n; i++) {
			if(vp[i].fi <= pos && pos <= vp[i].se) {
			} else {
				cnt++;
				pos = vp[i].se;
			}
		}
		res = min(res, cnt);
		vp[0].fi += w*2 + h*2;
		vp[0].se += w*2 + h*2;
	}
	cout << res << endl;

	return 0;
}