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 <vector>
using namespace std;
#define N 5010
struct rec{
    int x,y,f,l,r;
}a[N];
struct Seg{
    int l,r,id;
    Seg(){}
    Seg(int l,int r,int id):l(l),r(r),id(id){}
}seg[N];
int n,w,d,m;
vector<int> g[N];
void calc_WN(int i,int &k)
{
    int tmp=min(a[i].x,d-a[i].y);
    int x=a[i].x-tmp,y=a[i].y+tmp;
    if(x==0) k=y;
    else k=d+x;
}
void calc_EN(int i,int &k)
{
    int tmp=min(w-a[i].x,d-a[i].y);
    int x=a[i].x+tmp,y=a[i].y+tmp;
    if(x==w) k=d+w+d-y;
    else k=d+x;
}
void calc_ES(int i,int &k)
{
    int tmp=min(w-a[i].x,a[i].y);
    int x=a[i].x+tmp,y=a[i].y-tmp;
    if(x==w) k=d+w+d-y;
    else k=d+w+d+w-x;
}
void calc_WS(int i,int &k)
{
    int tmp=min(a[i].x,a[i].y);
    int x=a[i].x-tmp,y=a[i].y-tmp;
    if(x==0) k=y;
    else k=d+w+d+w-x;
}
void calc(int i)
{
    int x,y,tmp,p1=d,p2=d+w,p3=d+w+d;
    if(a[i].f==0)
    {
        calc_WN(i,a[i].l);
        calc_EN(i,a[i].r);
    }
    else if(a[i].f==1)
    {
        calc_EN(i,a[i].l);
        calc_ES(i,a[i].r);
    }
    else if(a[i].f==2)
    {
        calc_WS(i,a[i].l);
        calc_WN(i,a[i].r);
    }
    else
    {
        calc_ES(i,a[i].l);
        calc_WS(i,a[i].r);
    }
}
bool cmp(Seg &a,Seg &b)
{
    return a.l<b.l;
}
int num[N];
bool check(int mid)
{
    for(int i=1;i<=n;++i) num[i]=0;
    int cnt=0;
    for(int i=1;i<=mid;++i)
    {
        for(int x:g[i])
        {
            if(num[x]==0) ++cnt;
            ++num[x];
        }
    }
    if(cnt>=n) return true;
    for(int i=mid+1;i<=m;++i)
    {
        for(int x:g[i-mid])
        {
            --num[x];
            if(num[x]==0) --cnt;
        }
        for(int x:g[i])
        {
            if(num[x]==0) ++cnt;
            ++num[x];
        }
        if(cnt>=n) return true;
    }
    return false;
}
int main()
{
    char st[10];
    scanf("%d%d%d",&n,&w,&d);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d%s",&a[i].x,&a[i].y,st);
        if(st[0]=='N') a[i].f=0;
        else if(st[0]=='E') a[i].f=1;
        else if(st[0]=='W') a[i].f=2;
        else if(st[0]=='S') a[i].f=3;
        calc(i);
    }
//    for(int i=1;i<=n;++i) printf("%d %d %d ?\n",i,a[i].l,a[i].r);
    int cnt=0,z=w*2+d*2;
    for(int i=1;i<=n;++i)
        if(a[i].l<=a[i].r)
        {
            seg[++cnt]=Seg(a[i].l,a[i].r,i);
            seg[++cnt]=Seg(a[i].l+z,a[i].r+z,i);
        }
        else seg[++cnt]=Seg(a[i].l,a[i].r+z,i);
    sort(seg+1,seg+cnt+1,cmp);
//    for(int i=1;i<=cnt;++i) printf("%d %d %d %d !!\n",i,seg[i].l,seg[i].r,seg[i].id);
    int minr=seg[1].r,last=1;
    m=0;
    for(int i=2;i<=cnt;++i)
    {
        if(minr<seg[i].l)
        {
            ++m;
            for(int j=last;j<i;++j)
                g[m].push_back(seg[j].id);
            minr=seg[i].r;last=i;
        }
        else minr=min(minr,seg[i].r);
    }
    ++m;
    for(int i=last;i<=cnt;++i)
        g[m].push_back(seg[i].id);
//    for(int i=1;i<=m;++i)
//    {
//        printf("i %d : ",i);
//        for(int x:g[i]) printf("%d ",x);
//        printf("\n");
//    }
    int l=1,r=n,mid;
    while(l+1<r)
    {
        mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    if(check(l)) printf("%d\n",l);
    else printf("%d\n",r);
    return 0;
}