Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <cctype>
using namespace std;
typedef long long LL;
const int N = 1005;

int n , w , h;
pair<int , int> a[N] , b[N];

int id(int x , int y) {
    if (y == 0)
        return x;
    if (x == w)
        return w + y;
    if (y == h)
        return w + h + w - x;
    if (x == 0)
        return w + h + w + h - y;
    return -1;
}

int check(int x , int y , int dx , int dy) {
    int xx , yy , X , Y;
    if (dx == 1)
        xx = w - x;
    else
        xx = x;
    if (dy == 1)
        yy = h - y;
    else
        yy = y;
    int T = min(xx , yy);
    X = x + dx * T;
    Y = y + dy * T;
    return id(X , Y);
}
 
void work() {    
    scanf("%d%d%d" , &n , &w , &h);
    int L = 2 * (w + h);
    vector<int> Q;
    for (int i = 0 ; i < n ; ++ i) {
        int x , y , l , r;
        char dir[5];
        scanf("%d%d%s" , &x , &y , dir);
        
        if (*dir == 'E') {
            l = check(x , y , 1 , -1);
            r = check(x , y , 1 , 1);
        }
        if (*dir == 'N') {
            l = check(x , y , 1 , 1);
            r = check(x , y , -1 , 1);
        }
        if (*dir == 'W') {
            l = check(x , y , -1 , 1);        
            r = check(x , y , -1 , -1);            
        }
        if (*dir == 'S') {
            l = check(x , y , -1 , -1);        
            r = check(x , y , 1 , -1);            
        }        
        //if (l > r)
        //    r += L;
        //cout << l << ' ' << r << endl;
        a[i] = make_pair(l , r);
        Q.push_back(l);
        Q.push_back(r);
    }
    sort(Q.begin(), Q.end());
    Q.erase(unique(Q.begin(), Q.end()), Q.end());
    // sort(a , a + n);
    int m = 0;
    int ans;
    if (n == 0) ans = 0;
    else ans = 1 << 30;
    for (int c = 0; c < Q.size(); ++c) {
        int t = Q[c];
        vector<pair<int, int> > ver;
        for (int i = 0; i < n; ++i) {
            int l = a[i].first,  r = a[i].second;
            if ((l <= t && r >= t && l <= r) || (l >= t && r >= t && l > r) ||
                (l <= t && r <= t && l > r))
                continue;
            //if (t == 22) printf("%d %d\n", l, r);
            l = l - t;
            r = r - t;
            if (l < 0) l += L;
            if (r < 0) r += L;
            ver.push_back(make_pair(l, -r)); 
        }
        sort(ver.begin(), ver.end());
        int p = 0;
        for (int i = 0; i < ver.size(); ++i) {
            ver[i].second = -ver[i].second;
            while (p > 0 && ver[i].second <= ver[p - 1].second)
                --p;
            ver[p++] = ver[i];
        }
        int r = -1;
        int res = 1;
        for (int i = 0; i < p; ++i) {
            if (ver[i].first > r) {
                ++res;
                r = ver[i].second;
            }
            else continue;
        }
        ans = min(ans, res);
    }
    cout << ans << endl;
}

int main() {
    work();
    return 0;
}