Cod sursa(job #1702248)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 14 mai 2016 20:36:03
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <bits/stdc++.h>
#define vmax 100001
#define ll long long
using namespace std;
ifstream fin("zc.in");
ofstream fout("zc.out");
struct punct
{
    int x,y;
};
punct a[vmax*13];
int s[vmax*13];
int qx(punct a, punct b)
{
    return a.x<b.x || (a.x==b.x && a.y<b.y);
}
int n,m,i,x,y,f;
char d;
ll sol,nr;
int caut(int x, int y)
{
    int s=1,d=f,m,best;
    while(s<=d)
    {
        m=s+(d-s)/2;
        if(a[m].x<x)s=m+1,best=m;
        else
        if(a[m].x>x)d=m-1;
        else
        {
            if(a[m].y<=y)
            {
                s=m+1;
                best=m;
            }
            else
            if(a[m].y>y)d=m-1;
        }
    }
    return best;
}
int op(char d, ll nr)
{
    int f1,f2,c=0;
    if(d=='N')
        {
            f1=caut(x+nr,y);
            f2=caut(x+1,y);
            if(a[f2].x==a[f2-1].x && a[f2].y==a[f2-1].y)c=1;
            return s[f1]-s[f2]+c;
        }
    if(d=='S')
       {
            f1=caut(x-nr,y);
            f2=caut(x-1,y);
            if(a[f2].x==a[f2-1].x && a[f2].y==a[f2-1].y)c=1;
            return s[f1]-s[f2]+c;
       }
    if(d=='E')
    {
        f1=caut(x,y+nr);
        f2=caut(x,y+1);
        if(a[f2].x==a[f2-1].x && a[f2].y==a[f2-1].y)c=1;
        return s[f1]-s[f2]+c;
    }
    if(d=='V')
    {
        f1=caut(x,y-nr);
        f2=caut(x,y-1);
        if(a[f2].x==a[f2-1].x && a[f2].y==a[f2-1].y)c=1;
        return s[f1]-s[f2]+c;
    }
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        fin>>x>>y;
        a[++f].x=x;
        a[f].y=y;
        a[++f].x=x-2;
        a[f].y=y;
        a[++f].x=x-1;
        a[f].y=y-1;
        a[++f].x=x-1;
        a[f].y=y;
        a[++f].x=x-1;
        a[f].y=y+1;
        a[++f].x=x;
        a[f].y=y-2;
        a[++f].x=x;
        a[f].y=y-1;
        a[++f].x=x;
        a[f].y=y+1;
        a[++f].x=x;
        a[f].y=y+2;
        a[++f].x=x+1;
        a[f].y=y-1;
        a[++f].x=x+1;
        a[f].y=y;
        a[++f].x=x+1;
        a[f].y=y+1;
        a[++f].x=x+2;
        a[f].y=y;
    }
    sort(a+1,a+f+1,qx);
    for(i=1;i<=f;i++)
        s[i]=s[i-1]+(!(a[i].x==a[i-1].x && a[i].y==a[i-1].y));
    while(m--)
    {
        fin>>d>>nr;
        sol+=op(d,nr);
    }
    fout<<sol<<"\n";
    return 0;
}