Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define REP(i,n,N) for(int i=n;i<N;i++)
#define RREP(i,n,N) for(int i=N-1;i>=n;i--)
#define p(S) cout<<S<<endl;
#define CK(n,a,b) ((a)<=(n)&&(n)<=(b))
using namespace std;


int ans;
int N, w ,d;
set<int> st[1010];
pair<int, int> rpoint[1010], lpoint[1010];// 座標、id
int x[1010], y[1010];
char f[1010];
int main() {
    cin>>N>>w>>d;
    REP(i,0,N){
        cin >> x[i] >> y [i] >> f[i];
    }
    REP(i,0,N){
        // 清水君のコード
        lpoint[i].second = rpoint[i].second = i;
        if(f[i]=='N'){
            rpoint[i].first = x[i] + (d - y[i]);
            if(0 <= x[i] - (d-y[i])){
                lpoint[i].first = x[i] - (d - y[i]);
            }else{
                lpoint[i].first = x[i] - (d - y[i]) + 2*w + 2*d;
            }
        }else if(f[i]=='E'){
            rpoint[i].first = 2 * w + d - x[i] - y[i];
            lpoint[i].first = x[i] + (d - y[i]);
        }else if(f[i]=='S'){
            rpoint[i].first = 2 * w + d - x[i] + y[i];
            lpoint[i].first = 2 * w + d - x[i] - y[i];
        }else{// f[i] == 'W';
            rpoint[i].first = (2 * w + d + x[i] + y[i]) % (2*w + 2*d);
            lpoint[i].first = 2 * w + d - x[i] + y[i];
        }
    }
    REP(i,0,N){
        //p(lpoint[i].first);
//        cout<<lpoint[i].first<<" "<<rpoint[i].first<<endl;
    }
    sort(rpoint, rpoint+N);

    REP(i,0,N){
        int id = rpoint[i].second;
        REP(j,0,N){
            int op_id = rpoint[j].second;
            if(id==op_id) continue;
//            cout<<"op_id: "<<op_id<<" "<<lpoint[op_id].first <<", "<< rpoint[j].first<<endl;
            if(lpoint[op_id].first < rpoint[j].first){
                if(CK(rpoint[i].first, lpoint[op_id].first, rpoint[j].first)){
                    st[i].insert(op_id);
//                    cout<<"st_i: "<<i<<" <- "<<op_id<<endl;
                }
            }else{
                if(CK(rpoint[i].first, lpoint[op_id].first, 2*w+2*d) || (CK(rpoint[i].first, 0,  rpoint[j].first))){
                    st[i].insert(op_id);
//                    cout<<"st_i: "<<i<<" <- "<<op_id<<endl;
                }
            }
        }
    }
    ans = N;
    REP(i,0,N){
//        cout<<"start man id: "<<i<<":"<<endl;
        vector<bool> used(N,false);
        int cnt = 0;
        REP(k,i,N){
            int j=rpoint[k].second;
//            REP(ii,0,N){
//                cout<<used[ii]<<", ";
//            }
//            cout<<" -> ";
            if(used[j]) continue;
            used[j]=true;
            cnt++;
            for(int id: st[k]){// set
                used[id]=true;
            }
//            REP(ii,0,N){
//                cout<<used[ii]<<", ";
//            }
//            cout<<endl;
        }
        REP(k,0,i){
            int j=rpoint[k].second;
//            REP(ii,0,N){
//                cout<<used[ii]<<", ";
//            }
//            cout<<" -> ";
            if(used[j]) continue;
            used[j]=true;
            cnt++;
            for(int id: st[k]){// set
                used[id]=true;
            }
//            REP(ii,0,N){
//                cout<<used[ii]<<", ";
//            }
//            cout<<endl;
        }
        ans = min(ans, cnt);
    }
    p(ans);
    return 0;
}