Cod sursa(job #25758)

Utilizator blasterzMircea Dima blasterz Data 4 martie 2007 14:26:52
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 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);
	
}

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);
}


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=1;
		while(j<=n && oi[i].x>drept[j].x) j+=t;
		
		for(int p=j-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;
}