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);
      return make_pair(s, e);
    }
    case 'W': {
      int s = mappingX(x, y, 3);
      int e = mappingX(x, y, 0) + w + w + d + d;
      if(e > w + w + d + d) {
        s -= + w + w + d + d;
        e -= + w + w + d + d;
      }
      return make_pair(s, e);
    }
    }
    return make_pair(-10, -10);
  };
  
  auto sw = [](const pair<int,int> p) {
    return make_pair(p.second, p.first);
  };
  
  for(int i = 0; i < n; i++) {
    int x, y, d;
    char c;
    cin >> x >> y;
    cin >> c;
    ps.push_back(sw(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 wrap = [d,w](bool aug, int a) {
    return aug ? a + d + d + w + w : a;
  };

  auto contains = [d,w,&ps](int i, int x) {
    int s = ps[i].second;
    int e = ps[i].first;
    if(s <= x && x <= e) return true;
    int y = x + d + d + w + w;
    if(s <= y && y <= e) return true;
    int z = x - (d + d + w + w);
    if(s <= z && z <= e) return true;
    return false;
  };

  // locating clocks from i's view
  auto count = [&ps,n,&wrap,&contains](const int ii){
    int i = ii;
    int k = 0;
    int cnt = 0;
    while(k < n) {
      int e = ps[i].first; //wrap(i < ii, ps[i].first);
      int kk = k;
      k++;
      i = (i + 1) % n;
      while(k < n && contains(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;
}