Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
int dx[]={1,1,-1,-1};
int dy[]={-1,1,1,-1};
int Con(char c){
  if(c=='S')return 3;
  if(c=='E')return 0;
  if(c=='N')return 1;
  if(c=='W')return 2;
}
int x,y,X,Y,n,w,h,l,r,d,cnt,ans=1e7;
char c;
map<P,int>m;
void init(){
  r(i,w+1)m[P(0,i)]=cnt++;
  r(i,h+1)m[P(i,w)]=cnt++;
  r(i,w+1)m[P(h,w-i)]=cnt++;
  r(i,h+1)m[P(h-i,0)]=cnt++;
}
signed main(){
  vector<P>v;
  cin>>n>>w>>h;
  init();
  r(i,n){
    cin>>X>>Y>>c;
    d=Con(c);
    x=X;y=Y;
    while(0<x&&x<w&&0<y&&y<h){
      x+=dx[d];
      y+=dy[d];
    }
    l=m[P(y,x)];
    x=X;y=Y;
    while(0<x&&x<w&&0<y&&y<h){
      x+=dx[(d+1)%4];
      y+=dy[(d+1)%4];
    }
    r=m[P(y,x)];
    v.push_back(P(r,l));
  }
  sort(v.begin(),v.end());
  r(i,n){
    int now=v[i].first,count=1;
    for(int k=0,j=i;k<n;k++,j=(j+1)%n){
      r=v[j].first;
      l=v[j].second;
      if(l>r){
        if(!((l<=now&&now<=cnt)||(0<=now&&now<=r))){
          now=r;
          count++;
        }
      }
      else{
        if(!(l<=now&&now<=r)){
          now=r;
          count++;
        }
      }
    }
    ans=min(ans,count);
  }
  r(i,n)swap(v[i].first,v[i].second);
  r(i,n){
    v[i].first=cnt-v[i].first+1;
    v[i].second=cnt-v[i].second+1;
  }
  sort(v.begin(),v.end());
  r(i,n){
    int now=v[i].first,count=1;
    for(int k=0,j=i;k<n;k++,j=(j+1)%n){
      r=v[j].first;
      l=v[j].second;
      if(l>r){
        if(!((l<=now&&now<=cnt)||(0<=now&&now<=r))){
          now=r;
          count++;
        }
      }
      else{
        if(!(l<=now&&now<=r)){
          now=r;
          count++;
        }
      }
    }
    ans=min(ans,count);
  }
  cout<<ans<<endl;
}