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;
typedef pair<int,int> P;
int N,W,H,L;
vector<P> t;

bool check(P p,int a){
  if(p.first<p.second)
    return (p.first<=a&&a<=p.second);
  return (p.first<=a||a<=p.second);
}
int calcArg(int x,int y){
  if(x==0)return y;
  if(y==H)return H+x;
  if(x==W)return H+W+H-y;
  return H+W+H+W-x;
}

int calcLU(int x,int y){
  int d=min(x,H-y);
  return calcArg(x-d,y+d);
}
int calcLD(int x,int y){
  int d=min(x,y);
  return calcArg(x-d,y-d);
}
int calcRU(int x,int y){
  int d=min(W-x,H-y);
  return calcArg(x+d,y+d);
}
int calcRD(int x,int y){
  int d=min(W-x,y);
  return calcArg(x+d,y-d);
}

int solve(int si){
  int res=1,last=t[si].second;
  for(int i=si;i<si+N;i++){
    if(check(t[i],last)) continue;
    res++;
    last=t[i].second;
  }
  return res;
}

int main(){
  cin>>N>>W>>H;
  L=W+W+H+H;
  for(int i=0;i<N;i++){
    int x,y,s;
    char ch;
    P p;
    cin>>x>>y>>ch;
    if(ch=='N'){
      s=calcArg(x,H);
      p.first = (s-H+y+L)%L;
      p.second = (s-y+H)%L;
    }
    if(ch=='E'){
      s=calcArg(W,y);
      p.first = (s-W+x+L)%L;
      p.second = (s-x+W)%L;
    }
    if(ch=='S'){
      s=calcArg(x,0);
      p.first = (s-y+L)%L;
      p.second = (s+y)%L;
    }
    if(ch=='W'){
      s=calcArg(0,y);
      p.first = (s-x+L)%L;
      p.second = (s+x)%L;
    }
    
    t.push_back(p);
  }
  for(int i=0;i<N;i++) swap(t[i].first,t[i].second);
  sort(t.begin(),t.end());
  for(int i=0;i<N;i++) t.push_back(t[i]);
  for(int i=0;i<N+N;i++) swap(t[i].first,t[i].second);
  int ans = N;
  for(int i=0;i<N;i++)ans = min(ans,solve(i));
  cout<<ans<<endl;
  return 0;
}