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> PII;
#define MP make_pair

int N, W, H;
int f(int x, int y){
  if(y == 0) return x;
  if(x == W) return y+W;
  if(y == H) return W-x+W+H;
  return H-y+W+H+W;
}

int main(){
  cin >> N >> W >> H;
  vector<PII> range(N*2);
  for(int i=0;i<N;++i){
	int x, y; char c; cin >> x >> y >> c;
	y = H - y;
	vector<int> xs(4);
	int d = min(x, y);
	xs[0] = f(x-d, y-d);
	d = min(W-x, y);
	xs[1] = f(x+d, y-d);
	d = min(W-x, H-y);
	xs[2] = f(x+d, y+d);
	d = min(x, H-y);
	xs[3] = f(x-d, y+d);
	for(int i=0;i<4;++i)
	  if(c == "NESW"[i]){
		c = i;
		break;
	  }
	range[i] = MP(xs[c], xs[(c+1)%4]+1);
	//cout << range[i].first << "," << range[i].second << endl;
  }
  int HW = 2 * (H+W);
  for(int i=0;i<N;++i){
	if(range[i].first >= range[i].second){
	  range[i] = MP(range[i].first, range[i].second+HW);
	  range[N+i] = MP(range[i].first+HW, 2*HW+1);
	}
	else
	  range[N+i] = MP(range[i].first+HW, range[i].second+HW);
  }
  sort(range.begin(), range.end());
  //for(int i=0;i<N*2;++i)
  //cout << range[i].first << "," << range[i].second << endl;

  int ans = 1e9;
  for(int i=0;i<N;++i){
	int tmp = 0;
	int last = -1;
	for(int j=i;j<i+N;++j){
	  if(range[j].second <= last)
		last = range[j].second;
	  else if(last <= range[j].first){
		++tmp;
		last = range[j].second;
	  }
	}
	ans = min(ans, tmp);
  }
  cout << ans << endl;
  
  return 0;
}