Cod sursa(job #388970)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 31 ianuarie 2010 15:55:08
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <cstdio>
#define nmax 100010
#include <algorithm>
using namespace std;

pair<int, int> d1[nmax], d2[nmax];
int n, m;

int main()
{
	freopen("grendizer.in","r",stdin);
	freopen("grendizer.out","w",stdout);
	scanf("%d %d",&n,&m);
	int i, s, x, y, r;
	for (i=0; i<n; i++)
	{
		scanf("%d %d",&x,&y);
		d1[i]=make_pair(x+y,x);
		d2[i]=make_pair(y-x,y);
	}
	sort(d1, d1+n);
	sort(d2, d2+n);
	for (i=0; i<m; i++)
	{
		scanf("%d %d %d",&x,&y,&r);
		s = upper_bound(d1, d1+n, make_pair(x+y+r, x+r-1))-lower_bound(d1, d1+n, make_pair(x+y+r, x+1));
		s+= upper_bound(d1, d1+n, make_pair(x+y-r, x-1)) - lower_bound(d1, d1+n, make_pair(x+y-r, x-r+1));
		s+= upper_bound(d2, d2+n, make_pair(y-x+r, y+r))-lower_bound(d2, d2+n, make_pair(y-x+r, y));
		s+= upper_bound(d2, d2+n, make_pair(y-x-r, y)) - lower_bound(d2, d2+n, make_pair(y-x-r, y-r));
		printf("%d\n",s);
	}
}