Pagini recente » Cod sursa (job #326327) | Cod sursa (job #1782285) | Cod sursa (job #2586593) | Cod sursa (job #1561589) | Cod sursa (job #253674)
Cod sursa(job #253674)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;
struct punct
{
int x, y;
} v[200005];
int ab(int x) { return x >= 0 ? x : (-x); }
int dist(punct x, punct y)
{
return ab(x.x - y.x) + ab(x.y - y.y);
}
int cmp(struct punct x, struct punct y)
{
if (x.x == y.x) return x.y < y.y;
return x.x < y.x;
}
int caut(punct x, int r)
{
int p, u, m;
p = 1; u = N;
while (p <= u)
{
m = (p + u) / 2;
if (v[m].x >= x.x - r && v[m].x <= x.x + r) return m;
else if (v[m].x > x.x) u = m - 1;
else p = m + 1;
}
return m;
}
int main()
{
freopen("grendizer.in","r",stdin);
freopen("grendizer.out","w",stdout);
int i, m, st, dr, r, cnt;
punct xx;
scanf("%d %d",&N,&M);
for (i = 1; i <= N; i++)
scanf("%d %d", &v[i].x, &v[i].y);
sort(v + 1, v + N + 1, cmp);
for (i = 1; i <= M; i++)
{
scanf("%d %d %d", &xx.x, &xx.y, &r);
cnt = 0;
m = caut(xx, r);
st = m; dr = st + 1;
while (v[st].x >= xx.x - r && st >= 1)
{
if (dist(v[st], xx) == r) cnt++;
st--;
}
while (v[dr].x <= xx.x + r && dr <= N)
{
if (dist(v[dr], xx) == r) cnt++;
dr++;
}
printf("%d\n",cnt);
}
return 0;
}