Cod sursa(job #25385)

Utilizator blasterzMircea Dima blasterz Data 4 martie 2007 12:22:07
Problema Ograzi Scor 20
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 1.33 kb
#include <cstdio>
#include <string>
#include <cstdlib>
#include <algorithm>
using namespace std;


struct point { int x, y;};

point oi[100005], drept[50005];

int n, m, W, H;  // n=nr dreptunghiuri, m=nr oi, W=latime, H=inaltime
char aux[150001*15];


bool operator<(const point &a, const point &b)
{
	if(a.x<b.x) return 1;
	if(a.x==b.x && a.y<b.y) return 1;
	return 0;
}


void citire()
{
	freopen("ograzi.in", "r", stdin);
	scanf("%d %d %d %d\n", &n, &m, &W, &H);
	fread(aux, sizeof(char), 150001*15, stdin);
	char *p;
	int i;
	p=strtok(aux, " ");
	drept[1].x=atoi(p);
	p=strtok(0, " \n");
	drept[1].y=atoi(p);
	
	for(i=2;i<=n;i++)
	{
		p=strtok(0, " ");
		drept[i].x=atoi(p);
		p=strtok(0, " \n");
		drept[i].y=atoi(p);
	}
	
	for(i=1;i<=m;i++)
	{
		p=strtok(0, " ");
		oi[i].x=atoi(p);
		p=strtok(0, " \n");
		oi[i].y=atoi(p);
	}
sort(drept+1, drept+n+1);
	
}

int binar(int l, int r, point sh)
{
	int m=(l+r)>>1;
	if(sh.x>=drept[m].x && sh.y>=drept[m].y && sh.x<=drept[m].x+W && sh.y<=drept[m].y+H) return 1;
	
	if(l==r) return 0;
	
	if(sh.x<=drept[m].x) return binar(l, m, sh);
	else return binar(m+1, r, sh);
}


	



int main()
{
	citire();
int nr=0;
for(int i=1;i<=m;i++) if(binar(1, n, oi[i])) nr++;

freopen("ograzi.out", "w", stdout);
printf("%d\n", nr);

	
	return 0;
}