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;

const int maxn = 1005;

int n;
int w;
int d;
int len;
int ln;
int tln;
pair<int, int> pool[maxn << 1];
pair<int, int> seg[maxn];
pair<int, int> tmp[maxn << 1];
bool ok[maxn];

void input()
{
    cin >> w >> d;
    len = 2 * (w + d);
    tln = 0;
    for (int i = 1; i <= n; i++) {
        int x, y;
        int U, D, L, R;
        int st;
        int ed;
        char s[5];
        cin >> x >> y >> s;
        switch(s[0]) {
        case 'N':
            U = d - y;
            L = x;
            if (U == L) st = 0;
            else if (U < L) st = x - U;
            else st = len - (U - L);
            ed = st + 2 * U;
            break;
        case 'S':
            D = y;
            R = w - x;
            if (D == R) st = d + w;
            else if (D < R) st = d + w + (R - D);
            else st = d + w - (D - R);
            ed = st + 2 * D;
            break;
        case 'W':
            L = x;
            D = y;
            if (L == D) st = 2 * w + d;
            else if (L < D) st = 2 * w + d + (D - L);
            else st = 2 * w + d - (L - D);
            ed = st + 2 * L;
            break;
        case 'E':
            R = w - x;
            U = d - y;
            if (R == U) st = w;
            else if (R > U) st = w - (R - U);
            else st = w + (U - R);
            ed = st + 2 * R;
            break;
        }
        seg[i] = make_pair(st, ed);
        tmp[++tln] = make_pair(st, -i);
        tmp[++tln] = make_pair(ed, i);
    }
}

int calc()
{
    int ans = 0;
    bool vis[maxn];
    stack<int> q;
    memset(vis, 0, sizeof(vis));
    while (q.size()) q.pop();
    for (int i = 1; i <= ln; i++) {
        if (vis[abs(pool[i].second)]) continue;
        if (pool[i].second < 0) {
            q.push(-pool[i].second);
        } else {
            ans ++;
            while (q.size()) {
                vis[q.top()] = true;
                q.pop();
            }
        }
    }
    return ans;
}

void prepare()
{
    sort(tmp + 1, tmp + tln + 1);
}

void solve()
{
    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= n; i++) {
        int x = seg[i].first;
        ln = 0;
        for (int j = 1; j <= n; j++) {
            ok[j] = true;
            if (seg[j].second <= len) {
                if ((x <= seg[j].second && x >= seg[j].first) || (x == 0 && seg[j].second == len)) {
                    ok[j] = false;
                }
            } else {
                if (x >= seg[j].first || x <= seg[j].second % len) {
                    ok[j] = false;
                }
            }
        }
        for (int j = 1; j <= tln; j++) {
            if (ok[abs(tmp[j].second)]) {
                pool[++ln] = tmp[j];
            }
        }
        ans = min(ans, 1 + calc());
        x = seg[i].second;
        ln = 0;
        for (int j = 1; j <= n; j++) {
            ok[j] = true;
            if (seg[j].second <= len) {
                if ((x <= seg[j].second && x >= seg[j].first) || (x == 0 && seg[j].second == len)) {
                    ok[j] = false;
                }
            } else {
                if (x >= seg[j].first || x <= seg[j].second % len) {
                    ok[j] = false;
                }
            }
        }
        for (int j = 1; j <= tln; j++) {
            if (ok[abs(tmp[j].second)]) {
                pool[++ln] = tmp[j];
            }
        }
        ans = min(ans, 1 + calc());
    }
    cout << ans << endl;
}

int main()
{
    while (cin >> n) {
        input();
        prepare();
        solve();
    }
    return 0;
}