Cod sursa(job #25055)

Utilizator ionel71089lescai ionel ionel71089 Data 4 martie 2007 10:19:12
Problema Ograzi Scor 40
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 1.29 kb
#include<fstream.h>
ifstream f("ograzi.in");
ofstream g("ograzi.out");
typedef struct _puncte
	{
	long x,y;
	}Puncte;
Puncte og[50000],oi[100000],Oaie;
unsigned int n,m,w,h;
int comp(Puncte p1,Puncte p2)
	{
	if(p1.x>p2.x)return 1;
	if(p1.x<p2.x)return -1;
	if(p1.x==p2.x)
		{
		if(p1.y>p2.y)return 1;
		if(p1.y<p2.y)return -1;
		return 0;
		}
	return 0;
	}
void quick(int inf,int sup)
	{
	if(inf<sup)
		{
		Puncte p=og[inf],aux;
		int i=inf+1,j=sup;

		while(i<=j)
			{
			while(i<=sup && comp(og[i],p)<=0)i++;
			while(j>=inf && comp(og[j],p)>0)j--;
			if(i<j && i<=sup && j>=inf)
				{
				aux=og[i];
				og[i]=og[j];
				og[j]=aux;
				i++;
				j--;
				}
			}
		i--;
		og[inf]=og[i];og[i]=p;
		quick(inf,i-1);
		quick(i+1,sup);
		}
	}
int gasire(int inf,int sup)
	{
	if(inf>sup)return 0;
	int mij=(inf+sup)/2;
	if(og[mij].x<=Oaie.x && Oaie.x<=og[mij].x+w &&
		 og[mij].y<=Oaie.y && Oaie.y<=og[mij].y+h)return 1;
	else
		{
		if(comp(Oaie,og[mij])<0)return gasire(inf,mij-1);
		else return gasire(mij+1,sup);
		}
	}
int main()
{
int i;
f>>n>>m>>w>>h;
for(i=0;i<n;i++)
	f>>og[i].x>>og[i].y;
for(i=0;i<m;i++)
	f>>oi[i].x>>oi[i].y;
quick(0,n-1);
int intoi=0;
for(i=0;i<m;i++)
	{
	Oaie=oi[i];
	intoi+=gasire(0,n-1);
	}
g<<intoi;
g.close();
return 0;
}