Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

struct data{
	int l,r;
	data(){}
	data(int ll,int rr){
		l=ll;
		r=rr;
	}
	bool operator<(const data &d)const{
		if(r==d.r)return l<d.l;
		return r<d.r;
	}
};

int n,w,d;
vector<data> query;



int main(void){
	scanf("%d%d%d",&n,&w,&d);
	for(int i=0;i<n;i++){
		int x,y;
		char c;
		scanf("%d%d%*c%c",&x,&y,&c);
		if(c=='N'){
			int ll=x-(d-y);
			int rr=x+(d-y);
			if(ll<0)ll+=(w+d)*2;
			query.push_back(data(ll,rr));
		}
		if(c=='E'){
			int ll=w+d-y-(w-x);
			int rr=w+d-y+(w-x);
			query.push_back(data(ll,rr));
		}
		if(c=='S'){
			int ll=w+d+(w-x)-y;
			int rr=w+d+(w-x)+y;
			query.push_back(data(ll,rr));
		}
		if(c=='W'){
			int ll=w+d+w+y-x;
			int rr=w+d+w+y+x;
			if(rr>=(w+d)*2)rr-=(w+d)*2;
			query.push_back(data(ll,rr));
		}
	}
	sort(query.begin(),query.end());
	for(int i=0;i<n;i++){
		query.push_back(query[i]);
	}
	int res=n;
	for(int i=0;i<n;i++){
		int tmp=1,last=query[i].r;
		for(int j=1;j<n;j++){
			data dd=query[i+j];
			if(dd.l<dd.r){
				if(last<dd.l || dd.r<last){
					tmp++;
					last=dd.r;
				}
			}else{
				if(last<dd.l && dd.r<last){
					tmp++;
					last=dd.r;
				}
			}
		}
		res=min(res,tmp);
		//printf("%d %d %d %d\n",i,query[i].l,query[i].r,tmp);
	}
	printf("%d\n",res);
	return 0;
}