Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef pair<int,int> P;
int w,h;

int calc(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 LU(int x,int y){
  int d=min(x,h-y);
  return calc(x-d,y+d);
}

int RU(int x,int y){
  int d=min(w-x,h-y);
  return calc(x+d,y+d);
}

int RD(int x,int y){
  int d=min(w-x,y);
  return calc(x+d,y-d);
}

int LD(int x,int y){
  int d=min(x,y);
  return calc(x-d,y-d);
}

bool check(P a,int b){
  if(a.f<a.s&&(a.f<=b&&b<=a.s))return 1;
  if(a.f>a.s&&!(a.s<b&&b<a.f)) return 1;
  return 0;
}

int main(){
  int n;
  cin>>n>>w>>h;
  
  vector <P> lr;
  for(int i=0;i<n;i++){
    int x,y;
    char ch;
    cin>>x>>y>>ch;
    if(ch=='N')lr.push_back(P(LU(x,y),RU(x,y)));
    if(ch=='E')lr.push_back(P(RU(x,y),RD(x,y)));
    if(ch=='S')lr.push_back(P(RD(x,y),LD(x,y)));
    if(ch=='W')lr.push_back(P(LD(x,y),LU(x,y)));
  }

  for(int i=0;i<n;i++)swap(lr[i].f,lr[i].s);
  sort(lr.begin(),lr.end());
  for(int i=0;i<n;i++)swap(lr[i].f,lr[i].s);
  
  
  int ans=n;
  for(int i=0;i<n;i++){
    int cnt=1,pos=lr[i].s;
    for(int j=0;j<n;j++){
      int idx=(i+j)%n;
      if(check(lr[idx],pos))continue;
      cnt++;
      pos=lr[idx].s;
    }
    ans=min(ans,cnt);
  }
  cout <<ans<<endl;  
  

  return 0;
}