Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int n,w,d;
char tem[10];
int a[1000+10][2];
int get(int x,int y,int type)
{
    if(type==0)
    {
        int xx=min(x,y);
        x-=xx;y-=xx;
        if(x==0)return y;
        else return w+w+d+d-x;
    }
    else if(type==1)
    {
        int xx=min(x,d-y);
        x-=xx;
        y+=xx;
        if(x==0)return y;
        else return d+x;
    }
    else if(type==2)
    {
        int xx=min(w-x,d-y);
        x+=xx;y+=xx;
        if(y==d)return d+x;
        else return d+w+d-y;
    }
    else if(type==3)
    {
        int xx=min(w-x,y);
        x+=xx;y-=xx;
        if(x==w)return w+d+d-y;
        else return w+d+d+w-x;
    }
}
int ans=0;
struct P
{
    int x;
    bool l;
    int ori;
    bool operator <(const P &b)const
    {
        if(x!=b.x)return x<b.x;
        else return (l!=b.l)&&l;
    }
}p[4000+10];
bool vis[1000+10];
int sta[4000+10];
void solve(int st)
{
    int res=1;
    int tail=0;
    for(int i=1;i<=n;i++)
    {
        vis[i]=false;
        int new1=a[i][0]-st,new2=a[i][1]-st;
        while(new1<=-(w+w+d+d)){new1+=w+w+d+d;new2+=w+w+d+d;}
        if(new1<=0&&new2>=0)continue;
        p[tail++]=(P){new1,true,i};
        p[tail++]=(P){new2,false,i};
    }
    sort(p,p+tail);
    int m=tail;
    tail=0;
    for(int i=0;i<m;i++)
    {
        if(vis[p[i].ori])continue;
        if(p[i].l)
        {
            sta[tail++]=p[i].ori;
        }
        else
        {
            res++;
            while(tail)vis[sta[--tail]]=true;
        }
    }
    ans=min(ans,res);
}
int main()
{
    scanf("%d%d%d",&n,&w,&d);
    for(int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d%d%s",&x,&y,tem);
        if(tem[0]=='W')a[i][0]=get(x,y,0),a[i][1]=get(x,y,1);
        else if(tem[0]=='N')a[i][0]=get(x,y,1),a[i][1]=get(x,y,2);
        else if(tem[0]=='E')a[i][0]=get(x,y,2),a[i][1]=get(x,y,3);
        else if(tem[0]=='S')a[i][0]=get(x,y,3),a[i][1]=get(x,y,0);
        if(a[i][0]>a[i][1])a[i][0]-=w+w+d+d;
    }
    ans=0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        solve(a[i][0]);solve(a[i][1]);
    }
    printf("%d\n",ans);
    return 0;
}