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;

namespace {

    typedef double real;
    typedef long long ll;

    template<class U, class V> ostream& operator<<(ostream& os, const pair<U, V>& p) {
        return os << "(" << p.first << "," << p.second << ")";
    }
    template<class T> ostream& operator<<(ostream& os, const vector<T>& vs) {
        if (vs.empty()) return os << "[]";
        os << "[" << vs[0];
        for (int i = 1; i < vs.size(); i++) os << " " << vs[i];
        return os << "]";
    }
    template<class T> istream& operator>>(istream& is, vector<T>& vs) {
        for (auto it = vs.begin(); it != vs.end(); it++) is >> *it;
        return is;
    }

    int N, W, D;
    int p(int x, int y) {
        if (x == 0) return y;
        else if (x == W) return D + W + (D - y);
        else if (y == D) return D + x;
        else { assert(y == 0);
            return D + W + D + (W - x);
        }
    }
    int p(const pair<int, int>& s) {
        return p(s.first, s.second);
    }

    map<string, int> M;
    void init() { M["W"] = 0; M["N"] = 1; M["E"] = 2; M["S"] = 3; }

    pair<int, int> cr(int x, int y, string f) {
        vector< pair<int, int> > ds;

        if (x - y > 0) ds.push_back(make_pair(x - y, 0));
        else ds.push_back(make_pair(0, y - x));

        if (x - (D - y) > 0) ds.push_back(make_pair(x - (D - y), D));
        else ds.push_back(make_pair(0, x + y));

        if (x + D - y < W) ds.push_back(make_pair(x + D - y, D));
        else ds.push_back(make_pair(W, y + W - x));

        if (x + y < W) ds.push_back(make_pair(x + y, 0));
        else ds.push_back(make_pair(W, y - (W - x)));

        //cout << make_pair(x, y) << " -> " << ds << endl;

        int p0 = p(ds[ M[f] ]);
        int p1 = p(ds[ (M[f] + 1) % 4 ]);
        return make_pair(p0, p1);
    }

    vector< pair<int, int> > V;
    void input() {
        init();
        cin >> N >> W >> D;
        for (int i = 0; i < N; i++) {
            int x, y; string f;
            cin >> x >> y >> f;
            V.push_back(cr(x, y, f));
        }
        //cout << V << endl;
    }

    const int INF = 1<<28;

    bool contain(pair<int, int> s, int k) {
        int x = 2 * (W + D);
        s.first %= x; s.second %= x;
        k %= x;
        if (s.first > s.second) s.second += 2 * (W + D);
        return (s.first <= k && k <= s.second) || (s.first <= k + x && k + x <= s.second);
    }

    int calc(int index) {
        int k = V[index].second;
        vector< pair<int, int> > T;
        for (int i = 0; i < N; i++) {
            if (!contain(V[i], k)) {
                int x = V[i].first, y = V[i].second;
                if (x > y) y += 2 * (W + D);
                if (x < k) x += 2 * (W + D);
                if (y < k) y += 2 * (W + D);
                T.push_back(make_pair(x, y));
            }
        }
        sort(T.begin(), T.end());
        int c = 0;
        for (int i = 0, a = 0; a < T.size(); ) {
            int t = T[a].second;
            while (i < T.size() && T[i].first <= t) {
                i++;
                t = min(t, T[i].second);
            }
            //cout << make_pair(a, i) << " " << make_pair(T[a].first, t) << endl;
            a = i;
            c++;
        }
        //cout << "k: " << k << " " << "T: " << T  << " c: " << c << endl;
        return c;
    }

    void solve() {
        int ans = INF;
        for (int i = 0; i < V.size(); i++) {
            ans = min(ans, calc(i) + 1);
        }
        cout << ans << endl;
    }
}

int main() {
    input(); solve();
    return 0;
}