Cod sursa(job #1758871)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 18 septembrie 2016 00:11:20
Problema Grendizer Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream cin("grendizer.in");
ofstream cout("grendizer.out");

const int MAXN = 100000;

struct Point {
    int x;
    int y;

    Point() {}

    Point(int _x, int _y): x(_x), y(_y) {}

    bool operator < (const Point &other) const {
        if (x == other.x)
            return y < other.y;
        return x < other.x;
    }

    bool operator <= (const Point &other) const {
        if (x == other.x)
            return y <= other.y;
        return x <= other.x;
    }
};

int n;
Point v[2][1 + MAXN];

int BinarySearch(int which, int x, int y) {
    int answer = 0, step;
    for (step = 1; step <= n; step *= 2);
    for (step; step; step /= 2)
        if (answer + step <= n && v[which][answer + step] <= Point(x, y))
            answer += step;
    return answer;
}

int main() {
    int m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        v[0][i] = Point(x + y, y);
        v[1][i] = Point(y - x, y);
    }
    sort(v[0] + 1, v[0] + n + 1);
    sort(v[1] + 1, v[1] + n + 1);
    for (int i = 1; i <= m; i++) {
        int x, y, r;
        cin >> x >> y >> r;
        int answer = 0;
        answer = answer + BinarySearch(0, x + y - r, y) - BinarySearch(0, x + y - r, y - r);
        answer = answer + BinarySearch(1, y - x - r, y - 1) - BinarySearch(0, y - x - r, y - r - 1);
        answer = answer + BinarySearch(1, y - x + r, y + r) - BinarySearch(0, y - x + r, y);
        answer = answer + BinarySearch(0, x + y + r, y + r - 1) - BinarySearch(0, x + y + r, y - 1);
        cout << answer << "\n";
    }
    return 0;
}