Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <algorithm>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
int dtoi(char c) { // direction to index
    return c == 'N' ? 0 :
           c == 'S' ? 1 :
           c == 'E' ? 2 :
           c == 'W' ? 3 : -1;
}
int itoyl[] = { 1, -1, 1, -1 }; // direction index to difference of y of left edge
int itoxl[] = { -1, 1, 1, -1 };
int itoyr[] = { 1, -1, -1, 1 };
int itoxr[] = { 1, -1, 1, -1 };
int proj_ix(int y, int x, int h, int w) {
    if (x == 0) return y;
    if (y == h) return h + x;
    if (x == w) return h + w + (h-y);
    if (y == 0) return h + w + h + (w-x);
    return -1;
}
int proj(int y, int x, int dy, int dx, int h, int w) {
    while (proj_ix(y, x, h, w) == -1) {
        y += dy;
        x += dx;
    }
    return proj_ix(y, x, h, w);
}
bool proj_in(int i, int l, int r, int len) {
    if (l <= i and i <= r) return true;
    if (r < l and l <= i) return true;
    if (r < l and i <= r) return true;
    return false;
}
int greedy(int initial, int n, int len, vector<int> const & l, vector<int> const & r) {
    vector<pair<int,int> > intervals;
    repeat (i,n) {
        if (not proj_in(initial, l[i], r[i], len)) {
            intervals.push_back(make_pair((l[i] - initial + len) % len,
                                          (r[i] - initial + len) % len));
        }
    }
    sort(intervals.begin(), intervals.end());
    int result = 1 + not intervals.empty();
    int q = 1000000007;
    for (auto p : intervals) {
        if (q < p.first) {
            result += 1;
            q = p.second;
        } else {
            q = min(q, p.second);
        }
    }
    return result;
}
int main() {
    int n, w, h; cin >> n >> w >> h;
    vector<int> l(n), r(n); // [l, r]
    repeat (i,n) {
        int x, y; char c; cin >> x >> y >> c;
        int d = dtoi(c);
        l[i] = proj(y, x, itoyl[d], itoxl[d], h, w);
        r[i] = proj(y, x, itoyr[d], itoxr[d], h, w);
    }
    int result = 1000000007;
    repeat (i,n) {
        result = min(result, greedy(l[i],n,2*(w+h),l,r));
        result = min(result, greedy(r[i],n,2*(w+h),l,r));
    }
    cout << result << endl;
    return 0;
}