Cod sursa(job #657589)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 6 ianuarie 2012 19:57:43
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<cstdio>
#include<algorithm>

using namespace std;

pair <int,int> s[100001],d[100001];

int main()
{
    int n,m,r,i,x,y,sol=0;
    pair <int,int> *it1,*it2;

	freopen("grendizer.in","r",stdin);
	freopen("grendizer.out","w",stdout);

	scanf("%d%d",&n,&m);
	for(i=0;i<n;++i)
	{
        scanf("%d%d",&x,&y);
		s[i]=make_pair(x+y,y);
		d[i]=make_pair(x-y,y);
	}

	sort(s,s+n);
	sort(d,d+n);

	for (;m;--m)
	{
		scanf("%d%d%d",&x,&y,&r);

		it1=lower_bound(s,s+n,make_pair(x+y-r,y-r));
		it2=upper_bound(s,s+n,make_pair(x+y-r,y));
		sol=it2-it1;

		it1=lower_bound(s,s+n,make_pair(x+y+r,y));
		it2=upper_bound(s,s+n,make_pair(x+y+r,y+r));
		sol+=it2-it1;

		it1=upper_bound(d,d+n,make_pair(x-y+r,y-r));
		it2=lower_bound(d,d+n,make_pair(x-y+r,y));
		sol+=it2-it1;

		it1=upper_bound(d,d+n,make_pair(x-y-r,y));
		it2=lower_bound(d,d+n,make_pair(x-y-r,y+r));
		sol+=it2-it1;

		printf("%d\n",sol);
	}
	return 0;
}