Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define range(i, a, n) for(int (i) = (a); (i) < (n); (i)++)
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
using namespace std;
#define fst first
#define snd second
  
int n, len; 

int solve(vector<pair<int, int>> & lr){
    for(auto & e : lr) swap(e.fst, e.snd);
    sort(begin(lr), end(lr));
    for(auto & e : lr) swap(e.fst, e.snd);
    
    int ret = n;
    rep(i, n){
        int cur = 1;
        int rs = lr[i].snd, frs = rs;
  
        // cout << rs << endl;

        range(_, 1, n){
            int j = (i + _) % n;
  
            int cl = lr[j].fst, cr = lr[j].snd;
            // cout << cl << " " << cr << endl;
            if(cl >= cr){
                if(cl <= rs or rs <= cr){
                    continue;
                }
                if(cl <= frs or frs <= cr){
                    continue;
                }

            }
            else {
                if(cl <= rs and rs <= cr){
                    continue;
                }
                if(cl <= frs and frs <= cr){
                    continue;
                }
            }
  
            cur++;
            rs = cr;
        }
  
        ret = min(ret, cur);
    }


    return ret;
}
  
int main(void){
    int w, h; cin >> n >> w >> h;
  
    vector<pair<int, int>> lr(n);
    len = 2 * w + 2 * h;
    for(auto & e : lr){
        int x, y; cin >> x >> y;
        y = h - y;
        char f; cin >> f;
  
        int o, p;
        switch(f){
        case 'N': o = x;                 p = y;     break;
        case 'E': o = w + y;             p = w - x; break;
        case 'S': o = 2 * w + h - x;     p = h - y; break;
        case 'W': o = 2 * w + 2 * h - y; p = x;     break;
        }
  
        e.fst = (o - p + len) % len;
        e.snd = (o + p) % len;
    }
  
    int res = solve(lr);
  
    for(auto & e : lr){
        e.fst = (len - 1) - e.fst;
        e.snd = (len - 1) - e.snd;
    }
    for(auto & e : lr) swap(e.fst, e.snd);
    res = min(res, solve(lr));
  
    cout << res << endl;
  
    return 0;
}