Cod sursa(job #554268)

Utilizator indestructiblecont de teste indestructible Data 14 martie 2011 18:35:52
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <stdio.h>
#include <vector>
#define NMAX 50005
#define LMAX 55
#define MOD 666013
#define mp make_pair
#define pii pair <int,int>
#define pb push_back
using namespace std;
int n,m,w,h,x,y,rez,found;
struct pct{int a,b,c,d;};
pct A[NMAX];
char line[LMAX];
vector <int> H[MOD];
inline int cif(char x)
{
	return x>='0' && x<='9';
}
inline int code(int a,int b)
{
	return (a<<10)+b;
}
void read()
{
	fgets(line+1,LMAX,stdin);
	int poz=0;
	x=y=0;
	while (!cif(line[poz+1])) poz++;
	while (cif(line[poz+1])) x=x*10+line[++poz]-'0';
	while (!cif(line[poz+1])) poz++;
	while (cif(line[poz+1])) y=y*10+line[++poz]-'0';
}
inline int inside(int poz)
{
	return A[poz].a<=x && x<=A[poz].a+w && A[poz].b<=y && y<=A[poz].b+h;
}
void query(int a,int b)
{
	int i,poz,cod,ok=0;
	cod=code(a,b)%MOD;
	for (i=0; i<H[cod].size(); i++)
	{
		poz=H[cod][i];
		if (A[poz].c==a && A[poz].d==b)
		{
			ok=1;
			break ;
		}
	}
	if (ok)
		if (inside(poz))
			found=1,rez++;
}
int main()
{
	freopen("ograzi.in","r",stdin);
	freopen("ograzi.out","w",stdout);
	scanf("%d%d%d%d\n",&n,&m,&w,&h);
	int i,a,b,cod;
	for (i=1; i<=n; i++)
	{
		read();
		a=(int)(((double)x+w-0.5)/w);
		b=(int)(((double)y+h-0.5)/h);
		A[i].a=x; A[i].b=y; A[i].c=a; A[i].d=b;
		cod=code(a,b)%MOD;
		H[cod].pb(i);
	}
	for (i=1; i<=m; i++)
	{
		read();
		a=(int)(((double)x-0.5)/w);
		b=(int)(((double)y-0.5)/h);
		found=0;
		query(a,b);
		if (found) continue ;
		query(a+1,b);
		if (found) continue ;
		query(a,b+1);
		if (found) continue ;
		query(a+1,b+1);
	}
	printf("%d\n",rez);
	return 0;
}