Cod sursa(job #25415)

Utilizator damaDamaschin Mihai dama Data 4 martie 2007 12:32:19
Problema Ograzi Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 1.66 kb
#include <stdio.h>
#include <algorithm>
#define nmax 1000000

using namespace std;

struct point
{
	int x, y;
};

int n, m, w, h, sol, cnt;
point d[50001], o[100001], v[100001];

bool gasit(point);
bool cmpx(point one, point two)
{
	return one.x < two.x || (one.x == two.x && one.y < two.y);
}
bool cmpy(point one, point two)
{
	return one.y < two.y ||(one.y == two.y && one.x < two.x);
}

int main()
{
	freopen("ograzi.in","r",stdin);
	freopen("ograzi.out","w",stdout);
	
	int i;
	
	scanf("%d%d%d%d", &n, &m, &w, &h);
	
	for(i = 1; i <= n; ++i)
	{
		scanf("%d%d", &d[i].x, &d[i].y);
	}
	sort(d + 1, d + n + 1, cmpx);
	for(i = 1; i <= m; ++i)
	{
		scanf("%d%d", &o[i].x, &o[i].y);
		if(gasit(o[i]))
		{
			++sol;
		}
	}
	
	printf("%d", sol);
	
	return 0;
}

bool gasit(point p)
{
	int min = 1, mid, max = n, start = -1;
	
	while(min <= max)
	{
		mid = (min + max) / 2;
		if(p.x < d[mid].x)
		{
			max = mid - 1;
			continue;
		}
		if(p.x > d[mid].x + w)
		{
			min = mid + 1;
			continue;
		}
		if(p.x <= d[mid].x + w && p.x >= d[mid].x)
		{
			start = mid;
			max = mid - 1;
		}
	}
	
	if(start != -1)
	{
		while(cnt)
		{
			v[cnt].x = 0;
			v[cnt].y = 0;
			--cnt;
		}
		while(p.x <= d[start].x + w && p.x >= d[start].x)
		{
			v[++cnt] = d[start];
			++start;
		}
		sort(v + 1, v + cnt + 1, cmpy);	
		min = 1;
		max = cnt;
		while(min <= max)
		{
			mid = (min + max) / 2;
			if(v[mid].y <= p.y && v[mid].y + h >= p.y)
			{
				return 1;
			}
			if(v[mid].y < p.y)
			{
				min = mid + 1;
			}
			if(v[mid].y > p.y + h)
			{
				max = mid - 1;
			}
		}
		return 0;
	}
	return 0;
}