Cod sursa(job #253934)

Utilizator raduzerRadu Zernoveanu raduzer Data 6 februarie 2009 13:43:19
Problema Grendizer Scor 10
Compilator cpp Status done
Runda Stelele Informaticii 2009, clasele 9-10, ziua 1 Marime 3.05 kb
#include <cstdio>

const int MAX_N = 610;
const int MOD = 300;
const int L = 600;

int n, m;
int a1[MAX_N][MAX_N], a2[MAX_N][MAX_N];
int a[MAX_N][MAX_N];

void make1()
{
	int i, j, k;
	
	for (k = 0; k <= L; ++k)
	{
		i = 1, j = k;
		while (i <= L && i > 0 && j <= L && j >= 0)
		{
			a1[i][j] = a1[i - 1][j + 1] + a[i][j];
			++i;
			--j;
		}
	}
	
	for (k = 1; k <= L; ++k)
	{
		i = k, j = L - 1;
		
		while (i <= L && i > 0 && j < L && j >= 0)
		{
			a1[i][j] = a1[i - 1][j + 1] + a[i][j];
			++i;
			--j;
		}
	}
}

void make2()
{
	int i, j, k;
	
	for (k = 600; k > 0; --k)
	{
		i = k, j = 1;
		
		while (i <= L && i > 0 && j <= L && j > 0)
		{
			a2[i][j] = a2[i - 1][j - 1] + a[i][j];
			++i;
			++j;
		}
	}
	
	for (k = 1; k <= 600; ++k)
	{
		i = 1, j = k;
		
		while (i <= L && i > 0 && j <= L && j > 0)
		{
			a2[i][j] = a2[i - 1][j - 1] + a[i][j];
			++i;
			++j;
		}
	}
}

int main()
{
	int i, x, y, r;
	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 + MOD][y + MOD];
	}
	
	make1();
	make2();
	
	for (i = 1; i <= m; ++i)
	{
		scanf("%d %d %d", &x, &y, &r);
		
		int s = 0;
		
		//1
		int x1 = x, y1 = y - r;
		
		if (y1 < -300)
		{
			x1 -= (-300 - y1);
			y1 = -300;
		}
		
		int x2 = x - r, y2 = y;
		
		if (x1 < -300)
		{
			y1 -= (-300 - x1);
			x1 = -300;
		}
		if (x1 < -300 || x1 > 300 || y1 < -300 || y1 > 300 || x2 < -300 || x2 > 300 || y2 < -300 || y2 > 300)
		{
			printf("0\n");
			continue;
		}
		if (x1 >= x2 && y1 <= y2) s += a1[x1 + MOD][y1 + MOD] - a1[x2 + MOD][y2 + MOD];
		//
		
		//2
		x1 = x - r, y1 = y;
		
		if (x1 < -300)
		{
			y1 += (-300 - x1);
			x1 = -300;
		}
		
		x2 = x, y2 = y + r;
		
		if (y2 > 300)
		{
			x2 -= (y2 - 300);
			y2 = 300;
		}
		if (x1 < -300 || x1 > 300 || y1 < -300 || y1 > 300 || x2 < -300 || x2 > 300 || y2 < -300 || y2 > 300)
		{
			printf("0\n");
			continue;
		}
		if (x1 <= x2 && y1 <= y2) s += a2[x2 + MOD][y2 + MOD] - a2[x1 + MOD][y1 + MOD];
		//
		
		//3
		x1 = x, y1 = y + r;
		
		if (y1 > 300)
		{
			x1 += (y1 - 300);
			y1 = 300;
		}
		
		x2 = x + r; y2 = y;
		
		if (x2 > 300) 
		{
			y2 += (x2 - 300);
			x2 = 300;
		}
		if (x1 < -300 || x1 > 300 || y1 < -300 || y1 > 300 || x2 < -300 || x2 > 300 || y2 < -300 || y2 > 300)
		{
			printf("0\n");
			continue;
		}
		if (x1 <= x2 && y1 >= y2) s += a1[x2 + MOD][y2 + MOD] - a1[x1 + MOD][y1 + MOD] - a[x1 + MOD][y1 + MOD];
		//
		
		//4
		x1 = x + r; y1 = y;
		
		if (x1 > 300)
		{
			y1 -= (x1 - 300);
			x1 = 300;
		}
		
		x2 = x, y2 = y - r;
		
		if (y2 < -300)
		{
			x2 += (-300 - y2);
			y2 = -300;
		}
		if (x1 < -300 || x1 > 300 || y1 < -300 || y1 > 300 || x2 < -300 || x2 > 300 || y2 < -300 || y2 > 300)
		{
			printf("0\n");
			continue;
		}
		if (x1 >= x2 && y1 >= y2) s += a2[x1 + MOD][y1 + MOD] - a2[x2 + MOD][y2 + MOD] + a[x2 + MOD][y2 + MOD];
		//
		
		printf("%d\n", s);
	}
}