Cod sursa(job #1990433)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 11 iunie 2017 20:33:02
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

ifstream fin ("grendizer.in"); ofstream fout ("grendizer.out");

int n;
unordered_map <int, vector< int >> mpx, mpy;

int clin (const vector< int > &k, int pos) {
    return upper_bound(k.begin(), k.end(), pos) - k.begin();
}

int main() {
    int m;
    fin >> n >> m;

    for (int i = 1; i <= n; ++ i) {
        int x, y;
        fin >> x >> y;
        mpx[x + y].push_back(x - y);
        mpy[x - y].push_back(x + y);
    }

    for (auto &i : mpx) sort(i.second.begin(), i.second.end());
    for (auto &i : mpy) sort(i.second.begin(), i.second.end());

    for (int i = 1; i <= m; ++ i) {
        int x, y, r;
        int a, b, c, d;
        fin >> x >> y >> r;

        b = x + y + r; a = x + y - r;
        d = x - y + r; c = x - y - r;

        int sol = 0;
        if (mpx.find( a ) != mpx.end())
            sol += clin(mpx[ a ], d) - clin(mpx[ a ], c - 1);
        if (mpx.find( b ) != mpx.end())
            sol += clin(mpx[ b ], d) - clin(mpx[ b ], c - 1);

        if (mpy.find( d ) != mpy.end())
            sol += clin(mpy[ d ], b - 1) - clin(mpy[ d ], a);
        if (mpy.find( c ) != mpy.end())
            sol += clin(mpy[ c ], b - 1) - clin(mpy[ c ], a);

        fout << sol << "\n";
    }

    fout.close();
    return 0;
}