Cod sursa(job #995580)

Utilizator Detrol2kGuianu Leon Detrol2k Data 9 septembrie 2013 17:11:21
Problema Zota & Chidil Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.42 kb
#include <fstream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;

#define N_MAX 100010

struct punct {
    int x, y;
};

/////////// FUNCTIONS ///////////
void compute_all_traps(vector<punct>& traps) {
    punct aux_p;
    int aux_size = traps.size();

    for(int i = 0; i < aux_size; i++) {
        aux_p.x = traps.at(i).x;
        aux_p.y = traps.at(i).y;
        aux_p.x++, traps.push_back(aux_p);
        aux_p.x++, traps.push_back(aux_p);
        aux_p.x = traps.at(i).x;
        aux_p.y = traps.at(i).y;
        aux_p.x--, traps.push_back(aux_p);
        aux_p.x--, traps.push_back(aux_p);
        aux_p.x = traps.at(i).x;
        aux_p.y = traps.at(i).y;
        aux_p.y++, traps.push_back(aux_p);
        aux_p.y++, traps.push_back(aux_p);
        aux_p.x = traps.at(i).x;
        aux_p.y = traps.at(i).y;
        aux_p.y--, traps.push_back(aux_p);
        aux_p.y--, traps.push_back(aux_p);
        aux_p.x = traps.at(i).x;
        aux_p.y = traps.at(i).y;
        aux_p.y++, aux_p.x--, traps.push_back(aux_p);
        aux_p.x = traps.at(i).x;
        aux_p.y = traps.at(i).y;
        aux_p.y++, aux_p.x++, traps.push_back(aux_p);
        aux_p.x = traps.at(i).x;
        aux_p.y = traps.at(i).y;
        aux_p.y--, aux_p.x--, traps.push_back(aux_p);
        aux_p.x = traps.at(i).x;
        aux_p.y = traps.at(i).y;
        aux_p.y--, aux_p.x++, traps.push_back(aux_p);
    }
}

bool comparator(punct a, punct b) {
    if(a.x < b.x)
        return true;
    else if(a.x == b.x)
        if(a.y < b.y)
            return true;
        else
            return false;

    return false;
}

///////////// MAIN /////////////
int main() {
	ifstream fin("zc.in");
	ofstream fout("zc.out");

	int i, k, nr_traps, nr_moves, solution = 0;
	vector<punct> v, traps;
    punct aux_p;
    char c;

	// Read
	fin >> nr_traps >> nr_moves;

    for(i = 1; i <= nr_traps; i++) {
        fin >> aux_p.x >> aux_p.y;
        traps.push_back(aux_p);
    }


    // Compute
    compute_all_traps(traps);
    sort(traps.begin(), traps.end(), comparator);

    aux_p.x = aux_p.y = 0;
    for(i = 1; i <= nr_moves; i++) {
        fin >> c >> k;
        switch(c) {
            case 'N':
                    for(int j = 1; j <= k; j++) {
                        aux_p.y++;
                        if(binary_search(traps.begin(), traps.end(), aux_p, comparator))
                            solution++;
                    }
                    break;
            case 'S':
                    for(int j = 1; j <= k; j++) {
                        aux_p.y--;
                        if(binary_search(traps.begin(), traps.end(), aux_p, comparator))
                            solution++;
                    }
                    break;
            case 'E':
                    for(int j = 1; j <= k; j++) {
                        aux_p.x++;
                        if(binary_search(traps.begin(), traps.end(), aux_p, comparator))
                            solution++;
                    }
                    break;
            case 'V':
                    for(int j = 1; j <= k; j++) {
                        aux_p.x--;
                        if(binary_search(traps.begin(), traps.end(), aux_p, comparator))
                            solution++;
                    }
                    break;
        }
    }


	// Print
	fout << solution;
}