Cod sursa(job #253674)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 6 februarie 2009 11:01:17
Problema Grendizer Scor 20
Compilator cpp Status done
Runda Stelele Informaticii 2009, clasele 9-10, ziua 1 Marime 1.21 kb
#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;
}