Cod sursa(job #253841)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 6 februarie 2009 12:51:13
Problema Grendizer Scor 10
Compilator c Status done
Runda Stelele Informaticii 2009, clasele 9-10, ziua 1 Marime 2.08 kb
#include<stdio.h>
#define infile "grendizer.in"
#define outfile "grendizer.out"
#define max_mod 500
int m[max_mod*2+1][max_mod*2+1]; //matricea in care vom salva bombele
int n,t; //numarul de bombe si de teste

//deoarece matricea are doar coordonate pozitive, trebuie sa refacem coordonatele negative pt pozitiile alocate lor in matrice
int reface_coord(int x)
	{
	if(x<0) return ((-1)*x+max_mod);
	return x;
	}

//verifica daca punctul se afla in matrice
int verif(int x)
	{
	if(x<0||x>max_mod*2) return 0; //nu se afla
	return 1; //se afla
	}

//returneaza cumarul de bombe care se afla da distanta Mahnattan egala cu r fata de x y
int nr_bombe(int m[max_mod*2+1][max_mod*2+1], int x, int y, int r)
	{
	if(r>max_mod*2) return 0; //nu poate exista nicio bomba :P
	int s=0; //initial nu avem nicio bomba
	int i,j,x1,y1,x2,y2,x3,y3,x4,y4;
	for(i=x-r,j=y;i<=x;i++,j++)
		{
		//refacem coordonatele pt toate cele 4 diagonale
		x1=reface_coord(i); y1=reface_coord(j);
		x2=reface_coord(i); y2=reface_coord(y-(j-y));
		x3=reface_coord(x+(x-i)); y3=reface_coord(j);
		x4=reface_coord(x+(x-i)); y4=reface_coord(y-(j-y));
		//luam fiecare coordonate in parte...daca se incadreaza in matrice.....adaugam numarul de bombe din cutieuta :>
		if(verif(x1)&&verif(y1)) s+=m[x1][y1];
		if(verif(x2)&&verif(y2)&&y2!=j) s+=m[x2][y2];
		if(verif(x3)&&verif(y3)&&x3!=x) s+=m[x3][y3];
		if(verif(x4)&&verif(y4)&&x4!=x&&y4!=j) s+=m[x4][y4];
		}
	return s; //returnam numarul de bombe gasite
	}

int main()
{
int i,x,y,r;
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

scanf("%d %d",&n,&t); //numarul de bombe si numarul de teste
for(i=1;i<=n;i++)
	{
	scanf("%d %d",&x,&y); //avem bomba la coordonatele x,y
	x=reface_coord(x); y=reface_coord(y); //refacem coordonatele
	m[x][y]++; //crestem numarul de bombe din poozitie
	}
while(t--) //avem de rezolvat
	{
	scanf("%d %d %d\n",&x,&y,&r); //trebuie sa vedem cate bombe se afla la distanta r fata de x y
	printf("%d\n",nr_bombe(m,x,y,r)); //calculam si afisem numarul de bombe	
	}

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