Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;

int main(int argc, char *argv[])
{
  int n, w, d;
  cin >> n >> w >> d;
  vector<pair<int,int>> ps;
  // mapping to the south-west corner 
  auto mapping0 = [](int x, int y) {
    return x - y;
  };
  // mapping in one of four directions
  auto mappingX = [w,d,&mapping0](int x, int y, int dir) {
    switch(dir) {
    case 0 : { // (-1, -1)-direction
      int o = mapping0(x, y);
      return o; // o >= 0 ? o : w + w + d + d + o; // normalization
    }
    case 1 : { // (1, -1)-direction
      int o = mapping0(w-x, y); // flipping in x
      return w - o; // o >= 0 ? w - o : w + (- o);
    }
    case 2 : { // (1, 1)-direction
      int o = mapping0(w-x, d-y); // flipping in x and y
      return w + d + o; // o >= 0 ? w + d + o : w + d + o;
    }
    case 3 : { // (-1, 1)-direction
      int o = mapping0(x, d-y); // flipping in y
      return w + d + w - o; // o >= 0 ? w + d + w - o : w + d + w + -o;
    }
    return -1;
    }
  };
  // mapping to a range
  auto make_range = [w,d,&mappingX](int x, int y, char c) {
    switch(c){
    case 'N': return make_pair(mappingX(x, y, 2), mappingX(x, y, 3));
    case 'E': return make_pair(mappingX(x, y, 1), mappingX(x, y, 2));
    case 'S': {
      int s = mappingX(x, y, 0);
      int e = mappingX(x, y, 1);
      if(s < 0) { // normalize to non-negative
        s += d + d + w + w;
        e += d + d + w + w;
      }
      return make_pair(s, e);
    }
    case 'W': {
      int s = mappingX(x, y, 3);
      int e = mappingX(x, y, 0) + w + w + d + d;
      return make_pair(s, e);
    }
    }
    return make_pair(-10, -10);
  };
  
  for(int i = 0; i < n; i++) {
    int x, y, d;
    char c;
    cin >> x >> y;
    cin >> c;
    ps.push_back(make_range(x, y, c));
  }
  // a desk = a range on walls
  // a lock = a point on walls
  // todo: put points so that every range contains a point

  // sort the ranges
  sort(ps.begin(), ps.end());

  // shrink the region (endpoint ee) by the range r
  auto shrink = [d,w](bool aug, const pair<int,int> &r, int *ee) {
    int s = r.first + (aug ? (d + d + w + w) : 0);
    int e = r.second + (aug ? (d + d + w + w) : 0);
    if(s <= *ee) {
      *ee = min(*ee, e);
      return true;
    }
    return false;
  };
  // locating clocks from i's view
  auto count = [&ps,n,&shrink](const int ii){
    int i = ii;
    int k = 0;
    int cnt = 0;
    while(k < n) {
      int e = ps[i].second;
      k++;
      i = (i + 1) % n;
      while(k < n && shrink(i < ii, ps[i], &e)) {
        i = (i + 1) % n;
        k++;
      }
      cnt++;
    }
    return cnt;
  };

  int cnt = n; // at most n
  // possible starting points
  for(int i = 0; i < n; i++) {
    cnt = min(cnt, count(i));
  }
  cout << cnt << endl;
  return 0;
}