Cod sursa(job #685778)

Utilizator predator5047Butiu Alexandru Octavian predator5047 Data 21 februarie 2012 10:31:40
Problema Zota & Chidil Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

struct XY
{
    int x,y;
};

vector<XY> v;

void AddCpacana(XY xy);
bool cautare(XY xy);

bool compare(XY i1,XY i2)
{
    if(i1.x != i2.x)
        return (i1.x < i2.x);
    return (i1.y < i2.y);
}

int main()
{
    int n,m,dir,cel = 0;
    XY poz;
    poz.x = 0,poz.y = 0;
    char c;
    ifstream fin("zc.in");
    XY xy;
    fin >> n >> m;
    for(int i = 1;i <= n;++i )
    {
        fin>>xy.x>>xy.y;
        AddCpacana(xy);
    }
	/*
	for(int i = 0; i < v.size();++i)
    {
        cout << v[i].x <<' '<<v[i].y<<'\n';
    }
	cout << "\n\n\n";
	*/
    sort(v.begin(),v.end(),compare);
	/*
    for(int i = 0; i < v.size();++i)
    {
        cout << v[i].x <<' '<<v[i].y<<'\n';
    }

    cout << "\n\n";
	*/

    for(int i = 1; i <= m;++i)
    {
        fin >> c >> dir;
        //cout << c <<" "<<dir <<'\n';
        int dx,dy;
        if( c == 'N')
            dx = 0 , dy = 1;
        else if(c == 'E')
            dx = 1 , dy = 0;
        else if(c == 'V')
            dx = -1,dy = 0;
        else
            dx = 0, dy = -1;
        for(int k = 1; k <= dir ; ++k)
        {
            poz.x += dx,poz.y += dy;
           // cout << poz.x << " " << poz.y << '\n';
            if(cautare(poz) == true)
                cel++;
        }
    }

    fin.close();

    ofstream fout("zc.out");
    fout<<cel;
    fout.close();
    return 0;
}

bool cautare(XY xy)
{
    int low = 0 , high = v.size() - 1,mid;

    while(low <= high)
    {
        mid = (low + high) / 2;
        if(v[mid].x == xy.x && v[mid].y == xy.y)
            return true;
        else if((v[mid].x > xy.x) || (v[mid].x == xy.x && v[mid].y > xy.y))
            high = mid -1;
        else
            low = mid + 1;
    }
    return false;
}

void AddCpacana(XY xy)
{
    short dx[]={1,0,-1,0,2,0,-2,0,1,-1,1,-1};
    short dy[]={0,1,0,-1,0,2,0,-2,1,-1,-1,1};

    int n = sizeof(dx)/sizeof(short);
    XY aux;

    v.push_back(xy);

    for(int k = 0; k < n;++k)
    {
        aux.x = xy.x + dx[k],aux.y = xy.y + dy[k];
        v.push_back(aux);
    }
}