Cod sursa(job #1097380)

Utilizator andreiiiiPopa Andrei andreiiii Data 3 februarie 2014 13:11:13
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <algorithm>
#include <cstdio>
#define mp make_pair
#define PII pair<int, int>
#define x first
#define y second

using namespace std;

const int INF=2e-10+3;

vector <PII> a, b;

int modul(int k)
{
    if(k<0) return -k;
    return k;
}

int main()
{
    freopen("zc.in", "r", stdin);
    freopen("zc.out", "w", stdout);
    int n, m, i, j, k, x, y, sol=0;
    char dir;
    vector <PII>::iterator it;
    scanf("%d %d\n", &n, &m);
    for(i=1;i<=n;i++)
    {
        scanf("%d %d\n", &x, &y);
        for(j=-2;j<=2;j++)
        {
            for(k=-2;k<=2;k++)
            {
                if(modul(j)+modul(k)<3&&(x+j||y+k))
                {
                    a.push_back(make_pair(x+j, y+k));
                }
            }
        }
    }
    sort(a.begin(), a.end());
    for(it=a.begin()+1, k=0;it!=a.end();it++) if(*it!=*(it-1)) a[++k]=*it;
    a.resize(k+1);
    b.resize(k+1);
    for(i=0;i<a.size();i++) b[i]=mp(a[i].y, a[i].x);
    sort(b.begin(), b.end());
    for(x=y=0;m--;)
    {
        scanf("%c %d\n", &dir, &k);
        if(dir=='N')
        {
            sol+=upper_bound(a.begin(), a.end(), mp(x, y+k))-lower_bound(a.begin(), a.end(), mp(x, y));
            y+=k;
        }
        else if(dir=='E')
        {
            sol+=upper_bound(b.begin(), b.end(), mp(y, x+k))-lower_bound(b.begin(), b.end(), mp(y, x));
            x+=k;
        }
        else if(dir=='S')
        {
            sol+=upper_bound(a.begin(), a.end(), mp(x, y))-lower_bound(a.begin(), a.end(), mp(x, y-k));
            y-=k;
        }
        else
        {
            sol+=upper_bound(b.begin(), b.end(), mp(y, x))-lower_bound(b.begin(), b.end(), mp(y, x-k));
            x-=k;
        }
        it=upper_bound(a.begin(), a.end(), mp(x, y))-1;
        if(*it==mp(x, y)&&m) sol--;
    }
    printf("%d", sol);
}