Cod sursa(job #253946)

Utilizator savimSerban Andrei Stan savim Data 6 februarie 2009 13:48:06
Problema Grendizer Scor 10
Compilator cpp Status done
Runda Stelele Informaticii 2009, clasele 9-10, ziua 1 Marime 1.35 kb
#include <stdio.h>

#define MAX_N 100010
#define MAX_L 1010
#define lim 800
#define cor 3

int n, m, i, j, k, p, q, r, x, y, sum, x1, x2, y1, y2;
int a[MAX_L][MAX_L], s1[MAX_L][MAX_L], s2[MAX_L][MAX_L];

int main() {

	freopen("grendizer.in", "r", stdin);
	freopen("grendizer.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	for (i = 1; i <= n; i++) {
		scanf("%d %d", &x, &y);
		a[x + cor][y + cor]++;
		if (x + cor > p) p = x + cor;
		if (y + cor > q) q = y + cor;
	}

	for (i = 1; i < MAX_L; i++)
		for (j = 1; j < MAX_L; j++) {
			s1[i][j] = s1[i - 1][j - 1] + a[i][j];
			s2[i][j] = s2[i - 1][j + 1] + a[i][j];
		}
	
	for (i = 1; i <= m; i++) {
		scanf("%d %d %d", &p, &q, &r);
		p += cor; q += cor;
		sum = 0; 
		if (q - r > 0) sum -= a[p][q - r];
		if (q + r < lim) sum -= a[p][q + r];
		if (p - r > 0) sum -= a[p - r][q];
		if (p + r < lim) sum -= a[p + r][q];
		
		//suma pe directia 1
		if (q + r < lim) sum += s1[p][q + r];
		if (p - r - 1 > 0) sum -= s1[p - r - 1][q - 1];
		if (p + r < lim) sum += s1[p + r][q];
		if (q - r - 1 > 0) sum -= s1[p - 1][q - r - 1];
		
		//suma pe directia 2
		if (p + r < lim) sum += s2[p + r][q];
		if (q + r + 1 < lim) sum -= s2[p - q][q + r + 1];
		if (q - r > 0) sum += s2[p][q - r];
		if (p - r - 1 > 0) sum -= s2[p - r - 1][q + 1];
		
		printf("%d\n", sum);
	}
		
	
	return 0;
}