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;
vector<P> t;

bool check(P p,int a){
  if(p.first<p.second){
    return (p.first<=a&&a<=p.second);
  }else{
    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 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 calcLD(int x,int y){
  int d=min(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;
  for(int i=0;i<N;i++){
    int x,y;
    char ch;
    P p;
    cin>>x>>y>>ch;
    if(ch=='N'){
      p.first=calcLU(x,y);
      p.second=calcRU(x,y);
    }else if(ch=='E'){
      p.first=calcRU(x,y);
      p.second=calcRD(x,y);
    }else if(ch=='S'){
      p.first=calcRD(x,y);
      p.second=calcLD(x,y);
    }else if(ch=='W'){
      p.first=calcLD(x,y);
      p.second=calcLU(x,y);
    }
    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=1e9;
  for(int i=0;i<N;i++)ans=min(ans,solve(i));
  cout<<ans<<endl;
  return 0;
}