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;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

typedef pair<int, int> Pi;
typedef tuple<int, int, int> Ti;
typedef vector<int> vint;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

struct Point {
  int x, y;
  Point(){}
  Point(int x, int y):x(x), y(y){}
  Point operator + (const Point p) {
    return Point(x+p.x, y+p.y);
  }
  Point operator - (const Point p) {
    return Point(x-p.x, y-p.y);
  }
};

struct Man {
  Point p;
  int d;
  Man(){}
  Man(Point p, int d):p(p), d(d){}
};

struct Interval {
  int l, r;
  Interval(){}
  Interval(int l, int r):l(l), r(r){}
  Interval operator + (Interval i) {
    return Interval(l+i.l, r+i.r);
  }
  Interval operator - (Interval i) {
    return Interval(l-i.l, r-i.r);
  }
  bool operator < (const Interval &i) const {
    return l != i.l ? l < i.l : r < i.r;
  }
};

string D = "NESW";
Point dv[] = {
  Point(-1, 1),
  Point(1, 1),
  Point(1, -1),
  Point(-1, -1)
};

int n, w, h;
vector<Man> men;
vector<Interval> vec;

bool intersect(Point p) {
  return p.x<=0||w<=p.x||p.y<=0||h<=p.y;
}

int project(Point p) {
  if(p.y == 0) return p.x;
  if(p.x == w) return w+p.y;
  if(p.y == h) return w+h+(w-p.x);
  if(p.x == 0) return w+h+w+(h-p.y);
  assert(false);
}

Interval getInterval(Man man) {
  Point cpl = man.p, cpr = man.p;
  while(!intersect(cpl)) cpl = cpl+dv[(man.d+1)%4];
  while(!intersect(cpr)) cpr = cpr+dv[man.d];
  Interval res(project(cpl), project(cpr));
  return res;
}

bool contain(Interval i, int pos) {
  if(i.l <= pos && pos <= i.r) return true;
  if(i.r < i.l && pos <= i.r) return true;
  if(i.r < i.l && i.l <= pos) return true;
  return false;
}

int solve(int pos) {
  vector<Interval> rem;
  rep(i, n) {
    if(contain(vec[i], pos)) continue;
    int l = vec[i].l, r = vec[i].r;
    if(r < l) r += (w+h)*2;
    rem.push_back(Interval(l, r));
  }
  if(rem.empty()) return 1;
  sort(all(rem));
  int res = 2;
  int prev = inf;
  rep(i, rem.size()) {
    if(rem[i].l <= prev) chmin(prev, rem[i].r);
    else res++, prev = rem[i].r;
  }
  return res;
}

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  cin >> n >> w >> h;
  rep(i, n) {
    int x, y; char d;
    cin >> x >> y >> d;
    men.push_back(Man(Point(x, y), D.find(d)));
  }

  rep(i, n) {
    vec.push_back(getInterval(men[i]));
    //cout<<vec[i].l<<" "<<vec[i].r<<endl;
  }

  int ans = inf;
  rep(i, n) {
    chmin(ans, solve(vec[i].l));
    chmin(ans, solve(vec[i].r));
  }
  cout << ans << endl;

  return 0;
}