Cod sursa(job #995381)

Utilizator Detrol2kGuianu Leon Detrol2k Data 8 septembrie 2013 20:17:06
Problema Zota & Chidil Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.23 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;
	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);
    }

    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++;
                        v.push_back(aux_p);
                    }
                    break;
            case 'S':
                    for(int j = 1; j <= k; j++) {
                        aux_p.y--;
                        v.push_back(aux_p);
                    }
                    break;
            case 'E':
                    for(int j = 1; j <= k; j++) {
                        aux_p.x++;
                        v.push_back(aux_p);
                    }
                    break;
            case 'V':
                    for(int j = 1; j <= k; j++) {
                        aux_p.x--;
                        v.push_back(aux_p);
                    }
                    break;
        }
    }


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

    int solution = 0;
    for(i = 0; i < v.size(); i++) {
        if(binary_search(traps.begin(), traps.end(), v.at(i), comparator))
            solution++;
    }


	// Print
	fout << solution;
}