Cod sursa(job #170159)

Utilizator ScrazyRobert Szasz Scrazy Data 2 aprilie 2008 14:14:30
Problema Ograzi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>
#include <ext/hash_map>
using namespace std;
using namespace __gnu_cxx;

const int dx[4] = {0, 0, -1, -1};
const int dy[4] = {0, -1, 0, -1};

#define mp make_pair
#define pb push_back

int n, m, w, h; 

typedef pair<int,int> PII;

char s[40], *p;
int sol = 0;

vector<PII> P;

struct fn
{
    size_t operator()(const PII a) const
    {
	return a.first * 1000 + a.second;
    }
};

typedef hash_map< PII, int, fn > hash_type;
typedef hash_type :: iterator iter; 

hash_type hh;
iter it;

int get(void)
{
    int n;
    for (; *p == ' '; p++);

    for (n = 0; *p >= '0' && *p <='9'; p++)
	n = n*10 + *p-'0';

    for (; *p == ' '; p++);
    return n;
}

inline int ok(int ox, int oy, int a)
{
    return ox >= P[a].first && ox <= P[a].first + w &&
	   oy >= P[a].second && oy <= P[a].second + h;
}

int main()
{
    freopen("ograzi.in","r",stdin);
    freopen("ograzi.out","w",stdout);

    scanf("%d%d%d%d\n", &n, &m, &w, &h);
    for (int i = 0; i < n; ++i)
    {
	int xx, yy;
	gets(s); p = s;
	xx = get(); yy = get(); 
	++xx; ++yy;
	P.pb(mp(xx,yy)); 
	hh[ mp(xx / w, yy / h) ] = i; 
    }
    for (int i = 0; i < m; ++i)
    {
	int xx, yy;
	++xx; ++yy;
	gets(s); p = s;
	xx = get(); yy = get();
	PII oaie = mp(xx / w, yy / h); 
	for (int k = 0; k < 4; ++k)
	{
	    PII adj = mp(oaie.first - dx[k], oaie.second - dy[k]);
	    it = hh.find(adj);
	    if (it != hh.end())
		if (ok(xx, yy, (*it).second))
		{
		    ++sol;
		    break;
		}
	}
    }

    printf("%d\n", sol);

    return 0;
}