Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
// Template {{{
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;

#ifdef LOCAL
#include "contest.h"
#else
#define dump(x) 
#endif

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
inline bool valid(int x, int w) { return 0 <= x && x < w; }

void iostream_init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(12);
}
//}}}
struct Range{
    int b, e;
    bool operator < (const Range& r) const {
        if(b != r.b) return b < r.b;
        return e < r.e;
    }
};
int N, W, H;
int solve(vector<Range> ranges) {
    const int n = ranges.size();
    const int L = 2 * (W + H);
    sort(ranges.begin(), ranges.end(), [&](Range a, Range b){ if(a.e != b.e) return a.e < b.e; return a.b < b.b;});
    REP(i, n) ranges.push_back({ranges[i].b + L, ranges[i].e + L});
    int ans = INT_MAX;
    REP(s, n) {
        vector<pair<int, int>> events;
        REP(i, n) {
            events.push_back(make_pair(ranges[s+i].b, -(i+1)));
            events.push_back(make_pair(ranges[s+i].e, (i+1)));
        }
        sort(events.begin(), events.end());
        vector<bool> used(n);
        vector<int> list;
        int sub = 0;
        REP(i, events.size()) {
            int idx = abs(events[i].second) - 1;
            if(events[i].second < 0) {
                list.push_back(idx);
            } else {
                if(!used[idx]) {
                    sub++;
                    for(int x : list) {
                        used[x] = true;
                    }
                    list.clear();
                }
            }
        }
        ans = min(ans, sub);
    }
    return ans;
}
// int solve(vector<Range> ranges) {
//     sort(ranges.begin(), ranges.end());
//     vector<Range> rs;
//     vector<Range> rs2;
//     const int L = 2 * (W + H);
//     REP(i, ranges.size()) {
//         // if(rs.empty() || rs.back().e < ranges[i].e) {
//             rs.push_back(ranges[i]);
//             rs2.push_back({ranges[i].b + L, ranges[i].e + L});
//         // }
//     }
//     REP(i, rs2.size()) rs.push_back(rs2[i]);
//     sort(rs.begin(), rs.end(), [&](Range a, Range b){ if(a.e != b.e) return a.e < b.e; return a.b < b.b;});
//     int n = rs.size() / 2;
//     int ans = INT_MAX;
//     for(int s = 0; s < n; s++) {
//         int sub = 0;
//         for(int i = s; i < 2 * n;) {
//             if(i >= s + n) break;
//             const int take = rs[i].e;
//             while(i < s + n && rs[i].b <= take && take <= rs[i].e) {
//                 i++;
//             }
//             sub++;
//         }
//         ans = min(ans, sub);
//     }
//     return ans;
// }
void move(int& x, int& y, int dx, int dy) {
    int t = INT_MAX;
    if(dx == -1) t = min(t, x);
    if(dx == +1) t = min(t, (W-1) - x);
    if(dy == -1) t = min(t, y);
    if(dy == +1) t = min(t, (H-1) - y);
    x += t * dx;
    y += t * dy;
}
int convert(int x, int y) {
    if(x == 0 && y == 0) return 0;
    if(y == 0) {
        return x;
    }
    if(x == W - 1) {
        return W + y;
    }
    if(y == H - 1) {
        return W + H + (W - 1 - x);
    }
    assert(x == 0);
    return W + H + W + (H - 1 - y);
}
int main(){
    iostream_init();
    while(cin >> N >> W >> H) {
        W++; H++;
        vector<Range> ranges;
        REP(i, N) {
            int x, y;
            cin >> x >> y;
            string F;
            cin >> F;
            int lx = x, ly = y;
            int rx = x, ry = y;
            if(F == "N") {
                // up
                move(lx, ly, +1, +1);
                move(rx, ry, -1, +1);
            } else if(F == "E") {
                // right
                move(lx, ly, +1, -1);
                move(rx, ry, +1, +1);
            } else if(F == "S") {
                // down
                move(lx, ly, -1, -1);
                move(rx, ry, +1, -1);
            } else if(F == "W") {
                // left
                move(lx, ly, -1, +1);
                move(rx, ry, -1, -1);
            }
            int L = convert(lx, ly);
            int R = convert(rx, ry);
            if(L > R) R += 2 * (W + H); // ok ???
            ranges.push_back({L, R});
        }
        // REP(i, ranges.size()) {
        //     cout << "(" << ranges[i].b << "," << ranges[i].e << ") ";
        // }
        // cout << endl;
        cout << solve(ranges) << endl;
    }
    return 0;
}