Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define  fi first
#define  se second
#define  mk make_pair
#define  fr(i,x,y) for(i=x;i<=y;i++)
using namespace std;
typedef pair < int ,int > PII;
const int maxn=1010;
int n,w,d,ans,m;
PII a[maxn],b[maxn];
int Get(int x,int y,int dir)
{
	if(dir==1){
		if(x<y)return y-x;//(0,y-x)
		else return d+w+d+w-(x-y);//(x-y,0)
	}else if(dir==2){
		if(x<d-y)return y+x;//(0,y+x)
		else return d+x-(d-y);//(x-(d-y),d)
	}else if(dir==3){
		if(w-x<d-y)return d+w+d-(y+(w-x));//(w,y+(w-x))
		else return d+x+(d-y);//(x+(d-y),d)
	}else{
		if(w-x<y)return d+w+d-(y-(w-x));//(w,y-(w-x))
		else return d+w+d+w-(x+y);//(x+y,0)
	}
}
PII Get(int x,int y,char ch)
{
	int ret1,ret2;
	if(ch=='W'){
		ret1=Get(x,y,1);
		ret2=Get(x,y,2);
	}else if(ch=='N'){
		ret1=Get(x,y,2);
		ret2=Get(x,y,3);
	}else if(ch=='E'){
		ret1=Get(x,y,3);
		ret2=Get(x,y,4);
	}else{
		ret1=Get(x,y,4);
		ret2=Get(x,y,1);
	}
	return mk(ret1,ret2);
}
void Read()
{
	int i,x,y;
	char ch;
	scanf("%d%d%d",&n,&w,&d);
	fr(i,1,n)
	{
		scanf("%d%d%c%c",&x,&y,&ch,&ch);
		a[i]=Get(x,y,ch);
	}
}
int Cal(int x)
{
	if(x>=0)return x;
	return x+2*(w+d);
}
bool Cmp(const PII &x,const PII &y){return x.se<y.se;}
void Minn(int &x,int y){if(y<x)x=y;}
void Update(int x)
{
	int i,sum,la;
	m=0;
	fr(i,1,n)
		if(a[i].fi<a[i].se)
			if(a[i].fi<=x&&x<=a[i].se);
			else b[++m]=mk(Cal(a[i].fi-x),Cal(a[i].se-x));
		else
			if(x>=a[i].fi||x<=a[i].se);
			else b[++m]=mk(Cal(a[i].fi-x),Cal(a[i].se-x));
	if(m==0){Minn(ans,1);return;}
	sort(b+1,b+m+1,Cmp);
	sum=2;
	la=b[1].se;
	fr(i,2,m)
	{
		if(b[i].fi<=la)continue;
		la=b[i].se;
		sum++;
	}
	Minn(ans,sum);
}
void Solve()
{
	int i;
	ans=n;
	fr(i,1,n)
	{
		Update(a[i].fi);
		Update(a[i].se);
	}
	printf("%d\n",ans);
}
int main()
{
	Read();
	Solve();
}