Cod sursa(job #327727)

Utilizator Mishu91Andrei Misarca Mishu91 Data 29 iunie 2009 23:22:52
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
#include <algorithm>

using namespace std;

#define MAX_N 100004

int N, M;
pair <int, int> D1[MAX_N], D2[MAX_N];

ifstream fin("grendizer.in");
ofstream fout("grendizer.out");

void citire()
{
	fin >> N >> M;
	
	for(int i = 1; i <= N; ++i)
	{
		int x, y;
		fin >> x >> y;
		D1[i] = make_pair(x-y,y);
		D2[i] = make_pair(x+y,y);
	}
}

void solve()
{
	sort(D1+1, D1+N+1);
	sort(D2+1, D2+N+1);
	
	while(M--)
	{
		int x, y, r, sol(0);
		pair <int, int> *i1, *i2;
		fin >> x >> y >> r;
		
		i1 = lower_bound(D1+1, D1+N+1, make_pair(x-y-r,y));
		i2 = lower_bound(D1+1, D1+N+1, make_pair(x-y-r,y+r));
		
		sol += i2-i1;
		
		i1 = upper_bound(D1+1, D1+N+1, make_pair(x-y+r,y-r));
		i2 = upper_bound(D1+1, D1+N+1, make_pair(x-y+r,y));
		
		sol += i2-i1;
		
		i1 = lower_bound(D2+1, D2+N+1, make_pair(x+y-r,y-r));
		i2 = lower_bound(D2+1, D2+N+1, make_pair(x+y-r,y));
		
		sol += i2-i1;
		
		i1 = upper_bound(D2+1, D2+N+1, make_pair(x+y+r,y));
		i2 = upper_bound(D2+1, D2+N+1, make_pair(x+y+r,y+r));
		
		sol += i2-i1;
		
		fout << sol <<"\n";
	}
}

int main()
{
	citire();
	solve();
}