Pagini recente » Cod sursa (job #1155436) | Cod sursa (job #1485141) | Cod sursa (job #630575) | Cod sursa (job #1986418) | Cod sursa (job #1758871)
#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;
}