Cod sursa(job #79404)

Utilizator peanutzAndrei Homorodean peanutz Data 22 august 2007 02:14:16
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

typedef struct punct
{
	int x, y;
};

#define NMAX 100000

punct p[NMAX];
int n, nr;

void read()
{
	int i;
	scanf("%d", &n);
	for(i = 1; i <= n; ++i)
		scanf("%d%d", &p[i].x, &p[i].y);
}

bool comp(const punct& x, const punct& y)
{
	return (x.x < y.x || (x.x == y.x && x.y < y.y));
}

#define mid(st, dr) (((st)+(dr)) >> 1)
#define left(i) ((i) << 1)
#define right(i) (((i) << 1)+1)

int x1, y1, x2, y2, res;

int binary_search(int a, int b)
{
	int st, dr, keep1 = a-1, keep2 = a-1, m;

	st = a, dr = b;

	while(st <= dr)
	{
		m = mid(st, dr);

		if(p[m].y <= y1)
			keep1 = m, st = m+1;
		else
			dr = m-1;

		if(dr < 0)
			break;
	}

	st = a, dr = b;

	if(p[b].y <= y2)
		return b - keep1+1;

	while(st <= dr)
	{
		m = mid(st, dr);

		if(p[m].y <= y2)
			keep2 = m, st = m+1;
		else
			dr = m-1;

		if(dr < 0)
			break;
	}

	return keep2-keep1+1;
}

void query(int n, int st, int dr)
{
	if(p[st].x >= x1 && p[dr].x <= x2)
	{
		res += binary_search(st, dr);
		return ;
	}

	if(st == dr)
		return ;

	int m = mid(st, dr);

	if(x1 <= p[m].x)
		query(left(n), st, m);
	if(p[m].x < x2)
		query(right(n), m+1, dr);
}

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

	read();

	sort(p+1, p+n+1, comp);

	int i;
	scanf("%d", &nr);

	for(i = 1; i <= nr; ++i)
	{
		res = 0;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

		query(1, 1, n);

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

	return 0;
}