Cod sursa(job #997167)

Utilizator Detrol2kGuianu Leon Detrol2k Data 13 septembrie 2013 14:15:09
Problema Zota & Chidil Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.78 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

/////////// FUNCTIONS ///////////
void delete_duplicates(vector<pair<int, int> >& traps) {
    int nr = 0, length = traps.size();

    for(int i = 1; i < length; i++)
        if(traps[i - 1] == traps[i])
            nr++;
        else
            traps[i - nr] = traps[i];

    for(int i = 1; i <= nr; i++)
        traps.pop_back();
}

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

    const int tx[] = {-2, -1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 2};
    const int ty[] = {0, -1, 0, 1, -2, -1, 0, 1, 2, -1, 0, 1, 0};

	int i, j, x, y, x1, y1, k, nr_traps, nr_moves;
	long long solution = 0;
	vector<pair<int, int> > traps_x, traps_y;
	vector<pair<int, int> >:: iterator it1, it2;
    char c;

	// Read
	fin >> nr_traps >> nr_moves;

    traps_x.reserve(nr_traps * 13);
    traps_y.reserve(nr_traps * 13);
    for(i = 1; i <= nr_traps; i++) {
        fin >> x >> y;

        for(j = 0; j < 13; j++) {
            x1 = x + tx[j]; y1 = y + ty[j];
            if (x1 != 0 || y1 != 0) {
                traps_x.push_back(make_pair(x1, y1));
                traps_y.push_back(make_pair(y1, x1));
            }
        }
    }


    // Compute
    sort(traps_x.begin(), traps_x.end());
    sort(traps_y.begin(), traps_y.end());
    //delete_duplicates(traps_x);
    //delete_duplicates(traps_y);

    x = y = 0;
    for(i = 1; i <= nr_moves; i++) {
        fin >> c >> k;

        switch(c) {
            case 'N':
                    x1 = x; y1 = y + k;
                    it1 = upper_bound(traps_x.begin(), traps_x.end(), make_pair(x, y));
                    it2 = upper_bound(traps_x.begin(), traps_x.end(), make_pair(x1, y1));
                    break;
            case 'S':
                    x1 = x; y1 = y - k;
                    it1 = lower_bound(traps_x.begin(), traps_x.end(), make_pair(x1, y1));
                    it2 = lower_bound(traps_x.begin(), traps_x.end(), make_pair(x, y));
                    break;
            case 'E':
                    x1 = x + k; y1 = y;
                    it1 = upper_bound(traps_y.begin(), traps_y.end(), make_pair(y, x));
                    it2 = upper_bound(traps_y.begin(), traps_y.end(), make_pair(y1, x1));
                    break;
            case 'V':
                    x1 = x - k; y1 = y;
                    it1 = lower_bound(traps_y.begin(), traps_y.end(), make_pair(y1, x1));
                    it2 = lower_bound(traps_y.begin(), traps_y.end(), make_pair(y, x));
                    break;
        }

        solution += it2 - it1;
        x = x1, y = y1;
    }


	// Print
	fout << solution;
}