Cod sursa(job #25787)

Utilizator blasterzMircea Dima blasterz Data 4 martie 2007 14:38:06
Problema Ograzi Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <cstdio>
#include <string>
#include <cmath>
#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);
sort(oi+1, oi+m+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;
	int p=0;
	if(sh.x<=drept[m].x) p=binar(l, m, sh);
	if(sh.x>drept[m].x+W)p=max(p,binar(m+1, r, sh));
	return p;
}


void citire2()
{
	freopen("ograzi.in", "r", stdin);
	scanf("%d %d %d %d\n", &n, &m, &W, &H);
	for(int i=1;i<=n;i++) scanf("%d %d\n", &drept[i].x, &drept[i].y);
	for(int i=1;i<=m;i++) scanf("%d %d\n", &oi[i].x, &oi[i].y);
	sort(drept+1, drept+n+1);
	sort(oi+1, oi+m+1);
}




int main()
{
	citire();
long long nr=0;
for(int i=1;i<=m;i++)
/*
{
	
		int t=(int)sqrt(n);
		int j=t;
		while(j<=n && oi[i].x>drept[j].x) j+=t;
		
		if(j>=n)
		{
			for(int p=n-t-1;p<=n;p++)
				if(oi[i].x>=drept[p].x && oi[i].y>=drept[p].y && oi[i].x<=drept[p].x+W && oi[i].y<=drept[p].y+H){ nr++;break;}
		}
		else
		if(j==t+1)
		{
			for(int p=1;p<=t;p++)
				if(oi[i].x>=drept[p].x && oi[i].y>=drept[p].y && oi[i].x<=drept[p].x+W && oi[i].y<=drept[p].y+H){ nr++;break;}
		}
		
		else
		{
			
		for(int p=j-2*t-1;p<=j+1;p++) 
			if(oi[i].x>=drept[p].x && oi[i].y>=drept[p].y && oi[i].x<=drept[p].x+W && oi[i].y<=drept[p].y+H){ nr++;break;}
		}
		//for(int j=1;j<=n;j++) 
		//	if(oi[i].x>=drept[j].x && oi[i].y>=drept[j].y && oi[i].x<=drept[j].x+W && oi[i].y<=drept[j].y+H){ nr++;break;}
}
*/			
			if(binar(1, n, oi[i])) nr++;

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

	
	return 0;
}