Cod sursa(job #253931)

Utilizator ada_sAda-Mihaela Solcan ada_s Data 6 februarie 2009 13:41:03
Problema Grendizer Scor 30
Compilator cpp Status done
Runda Stelele Informaticii 2009, clasele 9-10, ziua 1 Marime 2.67 kb
#include <stdio.h>
#include <stdlib.h>

const long NMAX=100010;

struct elem
{
	long x, y;
};//elem

elem a[NMAX];

long cauta(long li, long ls, long c);
long partx(long jos, long sus);
void sortx(long jos, long sus);
long party(long jos, long sus);
void sorty(long jos, long sus);

int main()
{
	long n, m, i, j, dif[NMAX], nrDif=0, x1, y1, r, temp, cont, lm, aux;
	freopen("grendizer.in", "r", stdin);
	freopen("grendizer.out", "w", stdout);
	scanf("%ld%ld", &n, &m);
	for (i=0; i<n; i++)
		scanf("%ld%ld", &a[i].x, &a[i].y);
	sortx(0, n-1);
	dif[0]=0;
	nrDif=1;
	for (i=1; i<n; i++)
	  if (a[i].x!=a[i-1].x)
		  dif[nrDif++]=i;
	dif[nrDif]=n;
  for (i=0; i<nrDif; i++)
	  sorty(dif[i], dif[i+1]-1);
  for (i=0; i<m; i++)
	{
		scanf("%ld%ld%ld", &x1, &y1, &r);
		cont=0;
		for (j=0; j<nrDif; j++)
		{
			temp=r-abs(x1-a[dif[j]].x);
			if (temp>=0)
			{	
				lm=cauta(dif[j], dif[j+1]-1, y1+temp);
				if (lm>=0)
				{
					aux=lm;
					while ((aux>=0)&&(a[aux].x==a[lm].x)&&(a[aux].y==a[lm].y))
					{
						cont++;
						aux--;
					}//while
					aux=lm+1;
					while ((aux<n)&&(a[aux].x==a[lm].x)&&(a[aux].y==a[lm].y))
					{
						cont++;
						aux++;
					}//while					
				}//if
				if ((y1-temp)!=(y1+temp))
				{
					lm=cauta(dif[j], dif[j+1]-1, y1-temp);
					if (lm>=0)
					{
  					aux=lm;
	  				while ((aux>=0)&&(a[aux].x==a[lm].x)&&(a[aux].y==a[lm].y))
		  			{
							cont++;
							aux--;
						}//while
						aux=lm+1;
						while ((aux<n)&&(a[aux].x==a[lm].x)&&(a[aux].y==a[lm].y))
						{
							cont++;
							aux++;
						}//while												
					}//if
				}//if
			}//if
		}//for j
		printf("%ld\n", cont);
	}//for i	
	return 0;
}//main

long party(long jos, long sus)
{
	long p=jos, u=sus;
  elem t;
	while (p<u)
	{
		while ((a[p].y<=a[jos].y)&&(p<=u))
			p++;
		while ((a[u].y>a[jos].y)&&(p<=u))
			u--;
		if (p<u)
		{
    	t=a[p];
		  a[p]=a[u];
		  a[u]=t;
		}//if
	}//while
	t=a[jos];
	a[jos]=a[u];
	a[u]=t;
	return u;
}//party

void sorty(long jos, long sus)
{
	long p;
	if (jos<sus)
	{
	  p=party(jos, sus);
		sorty(jos, p-1);
		sorty(p+1, sus);
	}//if
}//sorty

long partx(long jos, long sus)
{
	long p=jos, u=sus;
  elem t;
	while (p<u)
	{
		while ((a[p].x<=a[jos].x)&&(p<=u))
			p++;
		while ((a[u].x>a[jos].x)&&(p<=u))
			u--;
		if (p<u)
		{
    	t=a[p];
		  a[p]=a[u];
		  a[u]=t;
		}//if
	}//while
	t=a[jos];
	a[jos]=a[u];
	a[u]=t;
	return u;
}//partx

void sortx(long jos, long sus)
{
	long p;
	if (jos<sus)
	{
	  p=partx(jos, sus);
		sortx(jos, p-1);
		sortx(p+1, sus);
	}//if
}//sortx

long cauta(long li, long ls, long c)
{
	long lm;
	while (li<=ls)
	{
  	lm=(li+ls)/2;		
		if (a[lm].y==c)
			return lm;
		else
			if (c<a[lm].y)
				ls=lm-1;
			else
				li=lm+1;
	}//while
	return -1;
}//cauta