Cod sursa(job #478512)

Utilizator freak93Adrian Budau freak93 Data 18 august 2010 22:49:53
Problema Zota & Chidil Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include<fstream>
#include<algorithm>
#define x first
#define y second

using namespace std;

const char iname[]="zc.in";
const char oname[]="zc.out";
const int maxn=100005;

ifstream f(iname);
ofstream g(oname);

int n,m,i,j,dx[13]={-2,-1,-1,-1,0,0,0,0,1,1,1,2,0},dy[13]={0,-1,0,1,-2,-1,1,2,-1,0,1,0,0},px[maxn],py[maxn],kx,ky,x,y,p,rez,r;
char c;
pair<int,int> a[maxn*13],op[maxn];

bool fcomp(pair<int,int> a,pair<int,int> b)
{
    if(a.y!=b.y)
        return a.y<b.y;
    return a.x<b.x;
}

int searchx(pair<int,int> v)
{
    int i,step;
    for(step=1;step<kx;step<<=1);
    for(i=0;step;step>>=1)
        if(i+step<=kx&&a[px[i+step]]<=v)
            i+=step;
    return i;
}

int searchy(pair<int,int> v)
{
    int i,step;
    for(step=1;step<ky;step<<=1);
    for(i=0;step;step>>=1)
        if(i+step<=ky&&fcomp(a[py[i+step]],v))
            i+=step;
    return i;
}

bool fcomp1(int x,int y)
{
    return a[x]<a[y];
}

bool fcomp2(int x,int y)
{
    return fcomp(a[x],a[y]);
}

int main()
{
    f>>n>>m;
    for(i=1;i<=n;++i)
    {
        f>>op[i].x>>op[i].y;
        for(j=0;j<13;++j)
            if(op[i].x+dx[j]!=0||op[i].y+dy[j]!=0)
                px[++kx]=r+1,py[++ky]=r+1,a[++r]=make_pair(op[i].x+dx[j],op[i].y+dy[j]);
    }
    sort(px+1,px+kx+1,fcomp1);
    n=1;
    for(i=2;i<=kx;++i)
        if(a[px[i]]!=a[px[i-1]])
            px[++n]=px[i];
    kx=n;

    sort(py+1,py+ky+1,fcomp2);
    n=1;
    for(i=2;i<=ky;++i)
        if(a[py[i]]!=a[py[i-1]])
            py[++n]=py[i];
    ky=n;

    f.get();
    x=y=0;
    for(i=1;i<=m;++i)
    {
        f>>c>>p;
        f.get();
        if(c=='N')
            rez+=searchx(make_pair(x,y+p))-searchx(make_pair(x,y)),y+=p;
        else
            if(c=='S')
                rez+=searchx(make_pair(x,y-1))-searchx(make_pair(x,y-p-1)),y-=p;
            else
                if(c=='E')
                    rez+=searchy(make_pair(x+p,y))-searchy(make_pair(x,y)),x+=p;
                else
                    rez+=searchy(make_pair(x-1,y))-searchy(make_pair(x-p-1,y)),x-=p;
    }
    g<<rez<<"\n";
}