Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <set>
using namespace std;
using T=tuple<int,int,int>;//i,r=0/l=1,i
int main(){
	int n,w,d;
	cin>>n>>w>>d;
	vector<T> V;
	for(int i=0;i<n;i++){
		int x,y; char dir;
		cin>>x>>y>>dir;
		if(dir=='N'){
			//left
			if(x+y<=d){
				V.emplace_back(2*w+2*d-(x+y),1,i);
			}else{
				V.emplace_back(2*w+d-(x+y-d),1,i);
			}
			//right
			if(y+w-x<=d){
				V.emplace_back(w+(y+w-x),0,i);
			}else{
				V.emplace_back(2*w+d-(x+d-y),0,i);
			}
		}else if(dir=='S'){
			//left
			if(x+y-w>=0){
				V.emplace_back(w+(x+y-w),1,i);
			}else{
				V.emplace_back(x+y,1,i);
			}
			//right
			if(y-x>=0){
				V.emplace_back(2*w+2*d-(y-x),0,i);
			}else{
				V.emplace_back(x-y,0,i);
			}
		}else if(dir=='E'){
			//left
			if(y+w-x<=d){
				V.emplace_back(w+(y+w-x),1,i);
			}else{
				V.emplace_back(2*w+d-(x+d-y),1,i);
			}			
			//right
			if(x+y-w>=0){
				V.emplace_back(w+(x+y-w),0,i);
			}else{
				V.emplace_back(x+y,0,i);
			}
		}else if(dir=='W'){
			//left
			if(y-x>=0){
				V.emplace_back(2*w+2*d-(y-x),1,i);
			}else{
				V.emplace_back(x-y,1,i);
			}
			//right
			if(x+y<=d){
				V.emplace_back(2*w+2*d-(x+y),0,i);
			}else{
				V.emplace_back(2*w+d-(x+y-d),0,i);
			}
		}
	}
	for(int i=0;i<2*n;i++){
		int a,b,c; tie(a,b,c)=V[i];
		V.emplace_back(a+2*w+2*d,b,c);
		V.emplace_back(a+4*w+4*d,b,c);
	}
	sort(V.begin(),V.end());
	/*
	for(auto v:V){
		int a,b,c; tie(a,b,c)=v;
		cout<<a<<' '<<b<<' '<<c<<endl;
	}*/
	int best = n+1;
	for(int j=0;j<2*n;j++){
		set<int> S;
		vector<int> Sta(n);//0:not covered, 1:covered
		int ans = 0;
		for(int i=j;i<j+2*n;i++){
			int loc,id,lr; tie(loc,lr,id)=V[i];
			if(lr==0){//r
				//S[id]=1;
				S.insert(id);
			}else{//l
				S.erase(id);
			}
		}
		for(int i=j+2*n;i<j+4*n;i++){
			int loc,id,lr; tie(loc,lr,id)=V[i];
			if(lr==0){//r
				//cout<<loc<<' '<<id<<endl;
				if(Sta[id]==0){
					S.insert(id);
				}
			}else{//l
				if(S.count(id)){
					ans++;
					for(auto &s:S){
						Sta[s]=1;
					}
					S.clear();
				}
			}
		}
		//cout<<ans<<endl;
		best=min(ans,best);
	}
	cout<<best<<endl;
	return 0;
}