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 long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define rdll(x) scanf("%lld",&x);
int n,w,h;
vector<P>vec;
vector<int>za;
bool in[400005];
bool cmp(P a,P b){
	return a.sc < b.sc;
}
vector<P>zwa;
int main(){
    cin>>n>>w>>h;
    	for(int i=0;i<w;i++){
    		//(i,0)
    		zwa.pb(mp(i,0));
    	}
    	for(int i=0;i<h;i++){
    		//(w,i)
    		zwa.pb(mp(w,i));
    	}
    	for(int i=w;i>0;i--){
    		//(i,h)
    		zwa.pb(mp(i,h));
    	}
    	for(int i=h;i>0;i--){
    		//(0,i)
    		zwa.pb(mp(0,i));
    	}
    rep(i,n){
    	int x,y; string st;
    	cin>>x>>y>>st;
    	int lb1,ub1;
    	if(st == "N" || st == "E"){
    		lb1 = x+y;
    		ub1 = w+h;
    	}
    	else{
    		lb1 = 0;
    		ub1 = x+y;
    	}
    	int lb2,ub2;
    	if(st == "S" || st == "E"){
    		lb2 = x-y;
    		ub2 = w;
    	}
    	else{
    		lb2 = -h;
    		ub2 = x-y;
    	}
    	//x+y; [lb1,ub1] x-y; [lb2,ub2]
    	vector<int>vecc;
    	for(int i=0;i<w;i++){
    		//(i,0)
    		if(i == x+y) vecc.pb(i);
    		if(i == x-y) vecc.pb(i);
    	}
    	for(int i=0;i<h;i++){
    		//(w,i)
    		if(w+i == x+y) vecc.pb(w+i);
    		if(w-i == x-y) vecc.pb(w+i);
    	}
    	for(int i=w;i>0;i--){
    		//(i,h)
    		if(i+h == x+y) vecc.pb(w+h+w-i);
    		if(i-h == x-y) vecc.pb(w+h+w-i);
    	}
    	for(int i=h;i>0;i--){
    		//(0,i)
    		if(i == x+y) vecc.pb(w+h+w+h-i);
    		if(-i == x-y) vecc.pb(w+h+w+h-i);
    	}
    	assert(vecc.size() == 4);
    	SORT(vecc);
    	int u = 0;
    	rep(i,4){
    		int L = vecc[i], R = vecc[(i+1)%4];
    		int w = (L+1)%zwa.size();
    		int X = zwa[w].fi, Y = zwa[w].sc;
    		if(lb1<=X+Y&&X+Y<=ub1&&lb2<=X-Y&&X-Y<=ub2){
	    		vec.pb(mp(L,R));
	    		za.pb(L); za.pb(R);
	    		u++;
	    	}
	}
	assert(u==1);
    }
    SORT(za); ERASE(za);
    rep(i,vec.size()){
    	vec[i].fi = lower_bound(za.begin(),za.end(),vec[i].fi)-za.begin();
    	vec[i].sc = lower_bound(za.begin(),za.end(),vec[i].sc)-za.begin();
    	if(vec[i].fi > vec[i].sc) vec[i].sc+=za.size();
    }
    int ans = INF;
    for(int i=0;i<za.size();i++){
        vector<P>nw;
        int cur = 0, ret = 1;
        rep(j,vec.size()){
            int a=vec[j].fi,b=vec[j].sc;
            {
                if(a<=i && i<=b);
                else if(a<=i+za.size() && i+za.size()<=b);
                else nw.pb(vec[j]);
            }
        }
        sort(nw.begin(),nw.end(),cmp);
        while(cur != nw.size()){
        	int las = nw[cur].sc; ret++;
        	while(cur != nw.size() && las >= nw[cur].fi) cur++;
    	}
    	ans = min(ans,ret);
    }
    cout<<ans<<endl;
}