Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for(int i = (int)(s); i < (int)(e); ++i)
#define rep(i, n) REP(i, 0, n)

#define fi first
#define se second

using P = pair<int, int>;
int n, w, h;
int L;

P calc(int x, int y, char c) {
    P ret;
    if(c == 'E') ret = {x+y, 2*w - x + y};
    else if(c == 'S') ret = {x - y, x + y};
    else if(c == 'W') ret = {L-x-y, L+x-y};
    else if(c == 'N') ret = {2*w-x+y, L-x-y};
    else assert(false);
    return ret;
}

int f(const vector<P>& d, int k) {
    int n = d.size();
    vector<P> v(n);
    rep(i, n) {
        v[i] = {d[i].fi - d[k].fi, d[i].se - d[k].fi};
        while(v[i].fi < 0) {
            v[i].fi += L;
            v[i].se += L;
        }
    }
    sort(v.begin(), v.end(), [&](const P& a, const P& b){return a.se < b.se;});
    int z = -1;
    int cnt = 0;
    for(auto&& p : v) {
        if(p.fi <= z) continue;
        else {
            z = p.se;
            cnt++;
        }
    }
    // cout << "k :" << k << endl;
    // rep(i, n) cout << v[i].fi << " " << v[i].se << endl;
    // cout << "cnt :" << cnt << endl;
    return cnt;
}


int main() {
    cin >> n >> w >> h;
    L = 2*w + 2*h;
    set<P> st;
    rep(i, n) {
        int x, y;
        char c;
        cin >> x >> y >> c;
        st.insert(calc(x, y, c));
    }
    // for(auto&& p : st) cout << p.fi << ", " << p.se << endl;
    vector<P> d;
    for(auto&& p : st) d.push_back(p);
    int ans = 1e9;
    rep(i, d.size()) {
        ans = min(ans, f(d, i));
    }
    cout << ans << endl;
    return 0;
}