Cod sursa(job #1555657)

Utilizator borcanirobertBorcani Robert borcanirobert Data 23 decembrie 2015 12:50:26
Problema Zota & Chidil Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

ifstream fin("zc.in");
ofstream fout("zc.out");

const int MAX = 100005;
const int INF = 0x3f3f3f3f;
const int obsi[] = { -2, -1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 2 };
const int obsj[] = { 0, -1, 0, 1, -2, -1, 0, 1, 2, -1, 0, 1, 0 };
const int di[] = { -1, 0, 1, 0 };
const int dj[] = { 0, 1, 0, -1 };

vector<pair<int, int>> o1;
vector<pair<int, int>> o2;
char D;
int p;
int N, M;
int no;
int nro;

int main()
{
	int i, j;
	int x, y, p, p1, p2;
	
	fin >> N >> M;
	for ( i = 1; i <= N; i++ )
	{
		fin >> x >> y;
		
		for ( j = 0; j < 13; j++ )
		{
			o1.push_back( make_pair( (x + obsi[j]), (y + obsj[j]) ) );
		}
	}
	sort( o1.begin(), o1.end() );
	
	for ( const auto& n : o1 )
		if ( o1[no] != n )
		{
			o1[++no] = n;
			o2.push_back( make_pair( n.second, n.first ) );
		}
	
	sort( o2.begin(), o2.end() );
	
	x = y = 0;
	for ( i = 1; i <= M; i++ )
	{
		fin >> D >> p;
				
		if ( D == 'E' )
		{
			nro += ( upper_bound( o2.begin(), o2.end(), make_pair(y, x + p) ) - lower_bound( o2.begin(), o2.end(), make_pair(y, x + 1) ) );
			x += p;
		}
		else
			if ( D == 'V' )
			{
				nro += ( upper_bound( o2.begin(), o2.end(), make_pair(y, x - 1) ) - lower_bound( o2.begin(), o2.end(), make_pair(y, x - p) ) );
				x -= p;
			}
			else
				if ( D == 'N' )
				{
					nro += ( upper_bound( o1.begin(), o1.end(), make_pair(x, y + p) ) - lower_bound( o1.begin(), o1.end(), make_pair(x, y + 1) ) );
					y += p;
				}
				else
					if ( D == 'S' )
					{
						nro += ( upper_bound( o1.begin(), o1.end(), make_pair(x, y - 1) ) - lower_bound( o1.begin(), o1.end(), make_pair(x, y - p) ) );
						y -= p;
					}
	}
	
	fout << nro << '\n';
	
	fin.close();
	fout.close();
	return 0;
}