Cod sursa(job #432832)

Utilizator nandoLicker Nandor nando Data 2 aprilie 2010 20:08:15
Problema Zota & Chidil Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <utility>
#include <vector>
#include <fstream>
#include <algorithm>
#include <iostream>

using namespace std;

#define NDIR 13

vector< pair<int,int> > vx, vy;

int n,m;

int dir[][2]={  {-2, 0},
        {-1,-1},{-1, 0},{-1,+1},
{ 0,-2},{ 0,-1},{ 0, 0},{ 0,+1},{ 0,+2},
	    {+1,-1},{+1, 0},{+1,+1},
			    {+2,0}};

void addPoint(int x,int y){
	for(int i=0;i<NDIR;i++){
		if(x+dir[i][0]!=0||y+dir[i][1]!=0){
			vx.push_back(make_pair(x+dir[i][0],y+dir[i][1]));
			vy.push_back(make_pair(y+dir[i][1],x+dir[i][0]));
		}
	}
}

bool compPts(pair<int,int> p1, pair<int,int> p2){
	return ((p1.first!=p2.first)?(p1.first<p2.first):(p1.second<p2.second));	
}



int main(){
	fstream fin("zc.in",ios::in);
	fstream fout("zc.out",ios::out);

	fin>>n>>m;

	int x,y,l,nb=0,b,e;
	char dir;
	for(int i=0;i<n;i++){
		fin>>x>>y;
		addPoint(x,y);
	}

	sort(vx.begin(),vx.end(),compPts);
	sort(vy.begin(),vy.end(),compPts);
	for(int i=0;i<vx.size();i++){
		printf("%d %d\n",vx[i].first,vx[i].second);
	}
	x=y=0;
	for(int i=0;i<m;i++){
		fin>>dir>>l;
		switch(dir){
			case 'N':
				b=lower_bound(vx.begin(),vx.end(),make_pair(x,y),compPts)-vx.begin();
				e=upper_bound(vx.begin(),vx.end(),make_pair(x,y+l),compPts)-vx.begin();
				if(e>=b&&vx[b].first==x&&y<=vx[b].second&&vx[b].second<=y+l){
					nb+=e-b;
				}
				y+=l;
				break;
			case 'V':
				b=lower_bound(vy.begin(),vy.end(),make_pair(y,x-l),compPts)-vy.begin();
				e=upper_bound(vy.begin(),vy.end(),make_pair(y,x),compPts)-vy.begin();
				if(e>=b&&vy[b].first==y&&x-l<=vy[b].second&&vy[b].second<=x){
					nb+=e-b;	
				}

				x-=l;
				break;
			case 'S':
				b=lower_bound(vx.begin(),vx.end(),make_pair(x,y-l),compPts)-vx.begin();
				e=upper_bound(vx.begin(),vx.end(),make_pair(x,y),compPts)-vx.begin();
				if(e>=b&&vx[b].first==x&&y-l<=vx[b].second&&vx[b].second<=y){
					nb+=e-b;
				} 
				y-=l;
				break;
			case 'E':
				b=lower_bound(vy.begin(),vy.end(),make_pair(y,x),compPts)-vy.begin();
				e=upper_bound(vy.begin(),vy.end(),make_pair(y,x+l),compPts)-vy.begin();
				if(e>=b&&vy[b].first==y&&x<=vy[b].second&&vy[b].second<=x+l){
					nb+=e-b;
				}

				x+=l;
				break;
		}
	}

	fout<<nb;

	fin.close();
	fout.close();
	return 0;
}