Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

struct Info{
	Info(int arg_start,int arg_end,int arg_id){
		start = arg_start;
		end = arg_end;
		id = arg_id;
	}

	bool operator<(const struct Info &arg) const{
		return end < arg.end;
	};
	int start,end,id;
};

struct Data{
	Data(int arg_start,int arg_end,int arg_id){
		start = arg_start;
		end = arg_end;
		id = arg_id;
	}
	bool operator<(const struct Data &arg) const{
		return start < arg.start;
	};
	int start,end,id;
};

int main(){

	int N,W,H;

	scanf("%d %d %d",&N,&W,&H);

	int x,y,tmp_start,tmp_end;
	char dir[2];

	vector<Info> V;
	vector<Data> D;

	for(int i = 0; i < N; i++){
		scanf("%d %d %s",&x,&y,dir);

		switch(dir[0]){
		case 'N':

			if(W-x+y > H){
				tmp_start = W+H+(W-(H+x-y));
			}else{
				tmp_start = W+W-x+y;
			}

			if(x+y > H){
				tmp_end = W+H+(W-(x+y-H));
			}else{
				tmp_end = W+H+W+(H-(x+y));
			}
			break;
		case 'E':

			if(-W+x+y < 0){
				tmp_start = x+y;
			}else{
				tmp_start = W + (-W+x+y);
			}

			if(W-x+y > H){
				tmp_end = W+H+(W-(H+x-y));
			}else{
				tmp_end	= W+W-x+y;
			}
			break;
		case 'W':

			if(x+y > H){
				tmp_start = W+H+(W-(x+y-H));
			}else{
				tmp_start = W+H+W+(H-(x+y));
			}

			if(-x+y < 0){
				tmp_end = x-y;
			}else{
				tmp_end = W+H+W+(H-(-x+y));
			}

			break;
		case 'S':

			if(-x+y < 0){
				tmp_start = x-y;
			}else{
				tmp_start = W+H+W+(H-(-x+y));
			}

			if(-W+x+y < 0){
				tmp_end = x+y;
			}else{
				tmp_end = W + (-W+x+y);
			}
			break;
		}
		V.push_back(Info(tmp_start,tmp_end,i));
		D.push_back(Data(tmp_start,tmp_end,i));
	}

	sort(V.begin(),V.end());

	int minimum = N,index;

	int clock_loc;


	for(int i = 0; i < N; i++){

		clock_loc = V[i].end;
		int tmp_count = 1;

		index = (i+1)%N;

		while(index != i){

			while((index != i) && ((V[index].start <= clock_loc && V[index].end >= clock_loc) ||
					(V[index].start > V[index].end && (V[index].start <= clock_loc || V[index].end >= clock_loc)))){
				index = (index+1)%N;
			}
			if(index != i){
				tmp_count++;
				clock_loc = V[index].end;
				index = (index+1)%N;
			}
		}

		minimum = min(minimum,tmp_count);
	}


	sort(D.begin(),D.end());

	for(int i = 0; i < N; i++){

		clock_loc = D[i].start;
		int tmp_count = 1;

		index = (i-1+N)%N;

		while(index != i){

			while((index != i) && ((D[index].start <= clock_loc && D[index].end >= clock_loc) ||
					(D[index].start > D[index].end && (D[index].start <= clock_loc || D[index].end >= clock_loc)))){
				index = (index-1+N)%N;
			}
			if(index != i){
				tmp_count++;
				clock_loc = D[index].start;
				index = (index-1+N)%N;
			}
		}
		minimum = min(minimum,tmp_count);
	}
	printf("%d\n",minimum);

	return 0;
}