Cod sursa(job #25726)

Utilizator skyelHighScore skyel Data 4 martie 2007 14:18:59
Problema Ograzi Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
//Vers 0.02 - Qsort+NsearchO

#include<fstream.h>
#define Nmax 100005
#define Mmax 50005
#define input "ograzi.in"
#define output "ograzi.out"

typedef struct
	{
	long x,y;
	}bydem;

bydem o[Nmax],og[Nmax],oaie[Mmax];
long n,m,w,h;

long dei(long p,long q)
	{
	int st=p, dr=q,x=o[p].x,y=o[p].y;
	while(st<dr)
		{
		while(st<dr&&o[dr].x>=x)dr--;
		o[st].x=o[dr].x;
		o[st].y=o[dr].y;
		while(st<dr&&o[st].x<=x)st++;
		o[dr].x=o[st].x;
		o[dr].y=o[st].y;
		}
	o[st].x=x;
	o[st].y=y;
	return st;
	}
void qsort(long p,long q)
	{
	int m=dei(p,q);
	if(m-1>p)
		qsort(p,m-1);
	if(m+1<q)
		qsort(m+1,q);
	}
int search(unsigned x,unsigned y)
	{
	long i;
	for(i=0;i<n;i++)
		{
		if(x>=o[i].x&&x<=og[i].x)
			if(y>=o[i].y&&y<=og[i].y)
				return 1;
		if(x<o[i].x)
			return 0;
		}
	return 0;
	}
int main()
	{
	int i;
	ifstream fin(input);
	ofstream fout(output);
	fin>>n>>m>>w>>h;
	for(i=0;i<n;i++)
		fin>>o[i].x>>o[i].y;
	qsort(0,n-1);
	for(i=0;i<n;i++)
		{
		og[i].x=o[i].x+w;
		og[i].y=o[i].y+h;
		}
	h=0;
	for(i=0;i<m;i++)
		{
		fin>>oaie[i].x>>oaie[i].y;
		if(search(oaie[i].x,oaie[i].y))
			h++;
		}
	fout<<h;
	return 0;
	}