Cod sursa(job #5659)

Utilizator zombie_testeala bala portocala si mandarina zombie_teste Data 13 ianuarie 2007 17:24:00
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <set>
#include <stdio.h>
#include <string.h>

using namespace std;

struct pereche
{
     int x, y;
} p;

const int ND = 13;
const int cx[] = {-2, -1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 2};
const int cy[] = {0, -1, 0, 1, -2, -1, 0, 1, 2, -1, 0, 1, 0};

int i, j, N, M;
int x, y, x1, y1, pas;
char dir;
long long Sol;

class in_ordine
{
     public:
     bool operator() (pereche p1, pereche p2)
     {    return ( (p1.x < p2.x) || (p1.x == p2.x && p1.y < p2.y) );   }
};

int main()
{
     set <pereche, in_ordine> Vx;
     set <pereche, in_ordine> Vy;
	 set <pereche, in_ordine> :: iterator it1, it2;
	 
	 freopen("zc.in", "r", stdin);
	 freopen("zc.out", "w", stdout);
	 
	 scanf("%d %d", &N, &M);
	 
	 for (i = 1; i <= N; i++)
	 {
			 scanf("%d %d\n", &x, &y);
			 
			 for (j = 0; j < ND; j++)
			 {
					 p.x = x + cx[j];
					 p.y = y + cy[j];
					 
					 if (p.x != 0 || p.y != 0) Vx.insert(p);
					 
					 p.x = y + cy[j];
					 p.y = x + cx[j];
					 
					 if (p.x != 0 || p.y != 0) Vx.insert(p);
			 }
	 }
	 
	 x = y = 0;
	 
	 for (it1 = Vx.begin(); it1 != Vx.end(); it1++) printf("%d %d\n", (*it1).x, (*it1).y);
	 
	 for (i = 1; i <= M; ++i) 
	 {
		scanf("%c %d", &dir, &pas);
		
		if (dir == 'S')
		{
				x1 = x; y1 = y - pas;
				
				p.x = x1; p.y = y1;
				it1 = Vx.lower_bound(p);
				
				p.x = x; p.y = y;
				it2 = Vx.lower_bound(p);
		}
		else
		if (dir == 'N')
		{
			
				x1 = x; y1 = y + pas;
				
				p.x = x; p.y = y;
				it1 = Vx.upper_bound(p);
				
				p.x = x1; p.y = y1;
				it2 = Vx.upper_bound(p);
		}
		else
		if (dir == 'V')
		{
				x1 = x - pas; y1 = y;
				
				p.x = y1; p.y = x1;
				it1 = Vy.lower_bound(p);
				
				p.x = y; p.y = x;
				it2 = Vy.lower_bound(p);
		}
		else
		if (dir == 'E')
		{
				x1 = x + pas; y1 = y;
				
				p.x = y; p.y = x;
				it1 = Vy.upper_bound(p);
				
				p.x = y1; p.y = x1;
				it2 = Vy.upper_bound(p);
		}
		else
		{
				x1 = x; y1 = y;
				
				it1 = Vx.begin(); it2 = Vx.begin();
		}

		Sol += it2 - it1;
		
		x = x1; y = y1;
	}

	 printf("%d\n", Sol);
	 
	 fclose(stdin);
	 fclose(stdout);
	 
	 return 0;
}