Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include<stdio.h>
#include<algorithm>
using namespace std;
char in[2];
pair<int,int> rng[110000];
int n;
pair<int,int> d[3100];
int calc(int st,int go){
	int ret=1;
	int now=st;
	for(int i=0;i<3*n;i++){
		if(d[i].second<=now)continue;
		if(d[i].first>=go)break;
		ret++;
		now=d[i].first;
	}
	return ret;
}
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	n=a;
	for(int i=0;i<a;i++){
		int x,y;
		scanf("%d%d%s",&x,&y,in);
		y=c-y;
		int X1,X2,Y1,Y2;
		if(in[0]=='E'){
			X1=x+y;
			X2=x+(c-y);
			Y1=0;
			Y2=c;
			if(X1>b){
				Y1+=X1-b;
				X1=b;
			}
			if(X2>b){
				Y2-=X2-b;
				X2=b;
			}
		}
		if(in[0]=='W'){
			X1=x-y;
			X2=x-(c-y);
			Y1=0;
			Y2=c;
			if(X1<0){
				Y1+=-X1;
				X1=0;
			}
			if(X2<0){
				Y2-=-X2;
				X2=0;
			}
			swap(X1,X2);
			swap(Y1,Y2);
		}	
		if(in[0]=='N'){
			X1=0;
			X2=b;
			Y1=y-x;
			Y2=y-(b-x);
			if(Y1<0){
				X1+=-Y1;
				Y1=0;
			}
			if(Y2<0){
				X2-=-Y2;
				Y2=0;
			}
		}
		if(in[0]=='S'){
			X1=0;
			X2=b;
			 Y1=y+x;
			 Y2=y+(b-x);
			if(Y1>c){
				X1+=Y1-c;
				Y1=c;
			}
			if(Y2>c){
				X2-=Y2-c;
				Y2=c;
			}
			swap(X1,X2);
			swap(Y1,Y2);
		}
		int z1,z2;
		if(Y1==0)z1=X1;
		else if(X1==b)z1=b+Y1;
		else if(Y1==c)z1=b+c+b-X1;
		else z1=b+c+b+c-Y1;
		if(Y2==0)z2=X2;
		else if(X2==b)z2=b+Y2;
		else if(Y2==c)z2=b+c+b-X2;
		else z2=b+c+b+c-Y2;
		rng[i]=make_pair(z1,z2);
	//	printf("%d %d, %d %d\n",X1,Y1,X2,Y2);
	}
	int ret=99999999;
	for(int i=0;i<a;i++){
		if(rng[i].first>rng[i].second)rng[i].second+=b*2+c*2;
	}
	for(int i=0;i<a;i++){
		d[i*3]=make_pair(rng[i].second,rng[i].first);
		d[i*3+1]=make_pair(rng[i].second+b*2+c*2,rng[i].first+b*2+c*2);
		d[i*3+2]=make_pair(rng[i].second+b*4+c*4,rng[i].first+b*4+c*4);
		
	}
	std::sort(d,d+a*3);
	for(int i=0;i<a;i++){
		ret=min(ret,calc(rng[i].first,rng[i].first+b*2+c*2));
		ret=min(ret,calc(rng[i].second,rng[i].second+b*2+c*2));
	}
	printf("%d\n",ret);
}