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
int n,w,h;
int pos(int x,int y){
  if(y==0) return x;
  if(y==h) return w+h+(w-x);
  if(x==0) return w+h+w+(h-y);
  if(x==w) return w+y;
  assert(0);
}
typedef pair<int,int> P;
signed main(){
  cin>>n>>w>>h;
  int x[n],y[n];
  char f[n];
  for(int i=0;i<n;i++) cin>>x[i]>>y[i]>>f[i];
  vector<P> v;
  for(int i=0;i<n;i++){
    int a,b,c,d;
    a=min(w-x[i],h-y[i]);
    b=min(w-x[i],y[i]);
    c=min(x[i],y[i]);
    d=min(x[i],h-y[i]);
    int l,r;
    if(f[i]=='E'){
      r=pos(x[i]+a,y[i]+a);
      l=pos(x[i]+b,y[i]-b);
    }
    if(f[i]=='S'){
      r=pos(x[i]+b,y[i]-b);
      l=pos(x[i]-c,y[i]-c);
    }
    if(f[i]=='W'){
      r=pos(x[i]-c,y[i]-c);
      l=pos(x[i]-d,y[i]+d);
    }
    if(f[i]=='N'){
      r=pos(x[i]-d,y[i]+d);
      l=pos(x[i]+a,y[i]+a);
    }
    if(r<l) r+=2*(w+h);
    v.push_back(P(l,r));
  }
 
  bool ovlp[n];
  for(int i=0;i<n;i++){
    ovlp[i]=0;
    for(int j=0;j<n;j++){
      ovlp[i]|=(i!=j)&&(v[i].first<=v[j].first&&v[j].second<=v[i].second);
      ovlp[i]|=(i!=j)&&(v[i].first<=v[j].first+2*(w+h)&&
			v[j].second+2*(w+h)<=v[i].second);
    }
    //cout<<i<<" "<<ovlp[i]<<endl;
  }
  
  for(int i=n-1;i>=0;i--) if(ovlp[i]) v.erase(v.begin()+i),n--;

  sort(v.begin(),v.end());
  for(int i=0;i<n;i++)
    v.push_back(P(v[i].first+2*(w+h),v[i].second+2*(w+h)));

  //for(int i=0;i<n;i++) cout<<v[i].first<<" "<<v[i].second<<endl;

  int ans=n;
  for(int i=0;i<n;i++){
    int tmp=0;
    int j=i,p;
    while(j<i+n){
      tmp++;
      p=v[j].second;
      while(j<i+n&&v[j].first<=p) j++;
    }
    //cout<<tmp<<endl;
    ans=min(ans,tmp);
  }
  cout<<ans<<endl;
  return 0;
}