Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;

struct Range{
    int l,r;
    bool contain(Range x){
        if(l<=r) return x.l<=x.r && l<=x.l && x.r<=r;
        else{
            if(x.l<=x.r) return l<=x.l || x.r<=r;
            else return l<=x.l && x.r<=r;
        }
    }
};

char dc[]="NESW";
int dx[]={-1,1,1,-1};
int dy[]={1,1,-1,-1};
int main(){
    int n,w,d;
    cin>>n>>w>>d;
    vector<int> x(n),y(n);
    vector<int> df(n);
    for(int i=0;i<n;i++){
        char f;
        cin>>x[i]>>y[i]>>f;
        for(int j=0;j<4;j++) if(dc[j]==f) df[i]=j;
        
    }
    auto crossPoint=[&](int px,int py,int dir){
        int ub=1000000;
        int lb=0;
        while(ub-lb>1){
            int mid=(ub+lb)/2;
            int tx=px+dx[dir]*mid;
            int ty=py+dy[dir]*mid;
            if(0<=tx && tx<=w && 0<=ty && ty<=d) lb=mid;
            else ub=mid;
        }
        return make_pair(px+dx[dir]*lb,py+dy[dir]*lb);
    };
    auto pos=[&](int x,int y){
        int sum=0;
        if(y==0) return x;
        sum+=w;
        if(x==w) return sum+y;
        sum+=d;
        if(y==d) return sum+w-x;
        sum+=w;
        return sum+d-y;
    };
    vector<Range> range(n);
    for(int i=0;i<n;i++){
        auto p=crossPoint(x[i],y[i],df[i]);
        int l=pos(p.first,p.second);
        p=crossPoint(x[i],y[i],(df[i]+1)%4);
        int r=pos(p.first,p.second);
        range[i]={r,l};
    }
    vector<int> reject(n,false);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i!=j && range[i].contain(range[j])){
                reject[i]=true;
            }
        }
    }

    {
        vector<Range> tmp;
        for(int i=0;i<n;i++){
            if(!reject[i]) tmp.push_back(range[i]);
        }
        range=tmp;
        n=range.size();
    }
    sort(range.begin(),range.end(),[](Range lhs,Range rhs){return lhs.l<rhs.l;});
    vector<int> kouho(n);
    for(int i=0;i<n;i++) kouho[i]=range[i].r;
    int res=n;
    for(int i=0;i<n;i++){
        Range p={kouho[i],kouho[i]};
        queue<Range> que;
        for(int j=0;j<n;j++){
            if(range[j].contain(p)){
                int prej=j;
                while(j<n && range[j].contain(p)){
                    j++;
                }
                for(int k=j;k<n;k++) que.push({range[k]});
                for(int k=0;k<prej;k++) que.push({range[k]});
                break;
            }
        }
        int cnt=1;
        while(!que.empty()){
            auto t=que.front(); que.pop();
            if(!t.contain(p)){
                cnt++;
                p={t.r,t.r};
            }
        }
        res=min(res,cnt);
    }
    cout<<res<<endl;
    return 0;
}