Cod sursa(job #492072)

Utilizator AncaPredeaPredea Anca AncaPredea Data 13 octombrie 2010 13:03:05
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <algorithm>
#include <stdio.h>

#define MAX 100010
#define mp make_pair
#define f first
#define s second

using namespace std;

int n, m;
pair <int, int> vctEl[2][MAX];

inline int cautaBin(int m, int fr, int ls, pair <int, int> key)
{
	if (fr > ls)
		return ls;
	int med = (fr + ls) / 2;
	
	if (vctEl[m][med] <= key)
		return cautaBin(m, med + 1, ls, key);
	else return cautaBin(m, fr, med - 1, key);
}

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

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);

		vctEl[0][i] = mp(x + y, y);
		vctEl[1][i] = mp(x - y, y);
	}

	sort(vctEl[0] + 1, vctEl[0] + n + 1);
	sort(vctEl[1] + 1, vctEl[1] + n + 1);

	for (int i = 1; i <= m; i++)
	{
		int x, y, r, sol = 0;
		scanf("%d %d %d", &x, &y, &r);

		sol += cautaBin(1, 1, n, mp(x - (y + r), y + r)) - cautaBin(1, 1, n, mp(x - (y + r), y));
		sol += cautaBin(1, 1, n, mp(x - (y - r), y)) - cautaBin(1, 1, n, mp(x - (y - r), y - r));
		sol += cautaBin(0, 1, n, mp(x + (y + r), y + r - 1)) - cautaBin(0, 1, n, mp(x + (y + r), y));
		sol += cautaBin(0, 1, n, mp(x + (y - r), y)) - cautaBin(0, 1, n, mp(x + (y - r), y - r - 1));

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

	fclose(stdin);
	fclose(stdout);
	return 0;
}