Cod sursa(job #253976)

Utilizator thebest001Neagu Rares Florian thebest001 Data 6 februarie 2009 13:58:13
Problema Grendizer Scor 10
Compilator cpp Status done
Runda Stelele Informaticii 2009, clasele 9-10, ziua 1 Marime 1.56 kb
#include <stdio.h>
#include <stdlib.h>
long a[100001][2];

int partitionare(int st,int dr)
{
	int m,p,i,j,aux;
	m=(st+dr)/2;
	p=a[m][0];
	i=st-1;
	j=dr+1;
	while (1)
	{
		while(a[++i][0]<p);
		while(a[--j][0]>p);
		if (i<j)
		{
			aux=a[i][0];
			a[i][0]=a[j][0];
			a[j][0]=aux;
			aux=a[i][1];
			a[i][1]=a[j][1];
			a[j][1]=aux;
		} else
		return j;
	}
}

void qsort(int st,int dr)
{
	int p;
	if (st<dr)
	{
		p=partitionare(st,dr);
		qsort(st,p);
		qsort(p+1,dr);
	}
}


int intre(int a,int b,int c)
{
	if (a<b && b<c)
		return 1;
	return 0;
}

int LOVIT(int catelea,int x,int y,int r)
{
	if (labs(x-a[catelea][1])+labs(y-a[catelea][0])==r)
		return 1;
	return 0;
}

int main()
{
	freopen("grendizer.in","r",stdin);
	freopen("grendizer.out","w",stdout);
	long m,n,r,x,y;
	scanf("%ld %ld",&m,&n);
	long i,j,cate=0;
	for (i=1;i<=m;i++)
	{
		scanf("%ld %ld",&a[i][0],&a[i][1]);

	}
	qsort(1,m);
	int aux;
	for (i=1;i<=m;i++)
		for (j=i;j<=m;j++)
		{
			if ((a[j-1][1]>a[j][1]) && a[j-1][0]==a[j][0])
			{
				aux=a[j-1][1];
				a[j-1][1]=a[j][1];
				a[j][1]=aux;
				aux=a[j-1][0];
				a[j-1][0]=a[j][0];
				a[j][0]=aux;
			}
		}
	for (i=2;i<=m+1;i++)
	{
		if (a[i-1][0]==a[i][0] && a[i-1][1]==a[i][1])
		{
				for (j=i+1;j<=m+1;j++)
				{
					a[j-1][0]=a[j][0];
					a[j-1][1]=a[j][1];
				}
				a[m][0]=0;a[m][1]=0;
			m--;
		}
	}
	for (i=1;i<=n;i++)
	{
		cate=0;
		scanf("%ld %ld %ld",&x,&y,&r);
		 for (j=1;j<=m;j++)
			if (LOVIT(j,x,y,r))
				cate++;
		printf("%ld\n",cate);
	}
	return 0;
}