Cod sursa(job #253886)

Utilizator ProtomanAndrei Purice Protoman Data 6 februarie 2009 13:21:21
Problema Grendizer Scor 30
Compilator cpp Status done
Runda Stelele Informaticii 2009, clasele 9-10, ziua 1 Marime 1.72 kb
// using ...hibride:)

#include <algorithm>
#include <stdio.h>

#define MAX 100010

using namespace std;

struct punct
{
	int x, y;
} vctPct[MAX];
int n, m, qMax;
int matPct[650][650];

int add(int x, int y)
{
	if (x >= 0 && x < 650 && y >= 0 && y < 650)
		return matPct[x][y];
	return 0;
}

int main()
{
	freopen("grendizer.in", "r", stdin);
	freopen("grendizer.out", "w", stdout);

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++)
	{
		scanf("%d %d", &vctPct[i].x, &vctPct[i].y);
		qMax = max(qMax, max(abs(vctPct[i].x), abs(vctPct[i].y)));
	}

	if (qMax < 300)
	{
		// primele 2 test:)
		for (; m; m--)
		{
			int x, y, r, rez = 0;
			scanf("%d %d %d", &x, &y, &r);

			for (int i = 1; i <= n; i++)
				if (abs(x - vctPct[i].x) + abs(y - vctPct[i].y) == r)
					rez++;

			printf("%d\n", rez);
		}
	}
	else
	{
		// poate si urmatoarele 3:)
		for (int i = 1; i <= n; i++)
		{
			vctPct[i].x += 300;
			vctPct[i].y += 300;
		}

		for (int i = 1; i <= n; i++)
			matPct[vctPct[i].x][vctPct[i].y]++;

		for (; m; m--)
		{
			int x, y, r, obGs = 0;
			scanf("%d %d %d", &x, &y, &r);
			x += 300;
			y += 300;
			r = min(r, 1201);

			if (r == 1201)
			{
				printf("0\n");
				continue;
			}

			// d - s
			for (int stx = x, sty = y + r; sty > y; stx++, sty--)
				obGs += add(stx, sty);

			// d - j
			for (int stx = x + r, sty = y; stx > x; stx--, sty--)
				obGs += add(stx, sty);

			// s - j
			for (int stx = x, sty = y - r; sty < y; stx--, sty++)
				obGs += add(stx, sty);

			// s - s
			for (int stx = x - r, sty = y; stx < x; stx++, sty++)
				obGs += add(stx, sty);

			printf("%d\n", obGs);
		}
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}