Cod sursa(job #282652)

Utilizator firewizardLucian Dobre firewizard Data 18 martie 2009 00:00:18
Problema Zota & Chidil Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.04 kb
#include <stdio.h>
#include <vector.h>
#include <algorithm>
char c,d;
int n,m,i,j,l,x,y,nr,k,nrc;
int cx[100005],cy[100005];
int indx[100005],indy[100005];
void sud(int);
void nord(int);
void vest(int);
void est(int);
void bifa(int x,int y)
{
 if (x&&y)cx[++l]=x;cy[l]=y;//center
 if (x+1&&y+1)cx[++l]=x+1;cy[l]=y+1;//dreapta sus
 if (x+1&&y)cx[++l]=x+1;cy[l]=y;//dreapta 1
 if (x+1&&y-1)cx[++l]=x+1;cy[l]=y-1;//dreapta jos
 if (x+2&&y)cx[++l]=x+2;cy[l]=y;//dreapta 2
 if (x&&y-1)cx[++l]=x;cy[l]=y-1;//jos 1
 if (x&&y-2)cx[++l]=x;cy[l]=y-2;//jos 2
 if (x&&y+1)cx[++l]=x;cy[l]=y+1;//sus 1
 if (x&&y+2)cx[++l]=x;cy[l]=y+2;//sus 2
 if (x-1&&y)cx[++l]=x-1;cy[l]=y;//stanga 1
 if (x-1&&y-1)cx[++l]=x-1;cy[l]=y-1;//stanga jos
 if (x-1&&y+1)cx[++l]=x-1;cy[l]=y+1;//stanga sus
 if (x-2&&y)cx[++l]=x-2;cy[l]=y;//stanga 2
}
int bsx(int x,int li,int ls)
{
    if(li==ls)return li;
    int m;
    m=(li+ls)/2;
    if (cx[indx[m]]==x)return m;
    else if (cx[indx[m]]<x)return bsx(x,m+1,ls);
         else return bsx(x,li,m);
}
int bsy(int x,int li,int ls)
{
    if(li==ls)return li;
    int i,m;
    m=(li+ls)/2;
    if (cy[indy[m]]==x)return m;
    else if (cy[indy[m]]<x)return bsy(x,m+1,ls);
         else return bsy(x,li,m);
}
int compx(const void *n1,const void *n2)
{
    return cx[*(int *)n1]-cx[*(int *)n2];
}
int compy(const void *n1,const void *n2)
{
    return cy[*(int *)n1]-cy[*(int *)n2];
}
int main()
{
    freopen ("zc.in","r",stdin);
    freopen ("zc.out","w",stdout);
    
//----------citire--marcaj---------//
    scanf ("%d %d",&n,&m);
    for (i=1;i<=n;++i){
        scanf ("%d %d\n",&x,&y);
        bifa(x,y);
        }
//----------citire--marcaj---------//

//--------preg sort+sort ----------//
    for (i=1;i<=l;++i){
        indx[i]=i;
        indy[i]=i;
        }
    qsort(indx+1,l,sizeof(int),compx);
    qsort(indy+1,l,sizeof(int),compy);
//--------preg sort+sort ----------//

    i=0;j=0;

//--------------traseu--------------//
    for (;m;--m){
        scanf ("%c %d\n",&c,&nr);
        if (c=='E')est(nr);
        if (c=='V')vest(nr);
        if (c=='N')nord(nr);
        if (c=='S')sud(nr);
        }
//--------------traseu---------------//

//-----------afisaje-----------------//
    printf ("%d\n",nrc);
//-----------afisaje-----------------//
    return 0;
}
void sud (int x)
{
    int li,ls;
    li=bsy(j-1,1,l);if (cy[indy[li]]!=j-1)li--;
    ls=bsy(j-x,1,l);
    for (k=ls;k<=li;++k)
        if(cx[indy[k]]==i)nrc++;
    j-=x;
}
void nord (int x)
{
    int li,ls;
    li=bsy(j+1,1,l);
    ls=bsy(j+x,1,l);if (cy[indy[li]]!=j+x)ls--;
    for (k=li;k<=ls;++k)
        if(cx[indy[k]]==i)nrc++;
    j+=x;
}
void vest (int x)
{
     int li,ls;
     li=bsx(i-1,1,l);if (cx[indx[li]]!=i-1)li--;
     ls=bsx(i-x,1,l);
     for (k=ls;k<=li;++k)
        if(cy[indx[k]]==j)nrc++;
    i-=x;
}
void est (int x)
{
     int li,ls;
     li=bsx(i+1,1,l);
     ls=bsx(i+x,1,l);if (cx[indx[li]]!=i+x)ls--;
     for (k=li;k<=ls;++k)
        if(cy[indx[k]]==j)nrc++;
    i+=x;
}