Cod sursa(job #25312)

Utilizator scapryConstantin Berzan scapry Data 4 martie 2007 11:55:32
Problema Ograzi Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 1.66 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <utility>
#include <ext/hash_map>
using namespace std;
using namespace __gnu_cxx;

enum { maxboxes = 50001, maxobjects = 100001 };

int boxes, objects;
int w, h;
int box[maxboxes][2];
int ans;

struct hash_f
{
	size_t operator()(const pair<int, int> b) const
	{
		return b.first * 1000 + b.second;
	}
};

hash_map< pair<int, int>, int, hash_f > map;
typedef hash_map< pair<int, int>, int, hash_f >::iterator iter;

inline bool in_box(int oi, int oj, int b)
{
	return oi >= box[b][0] && oi <= box[b][0] + w &&
	       oj >= box[b][1] && oj <= box[b][1] + h;
}

int main()
{
	int i;
	int ci, cj;
	int ai, aj;
	iter it;
	char buf[80];
	pair<int, int> obj, adj;
	FILE *f = fopen("ograzi.in", "r");
	if(!f) return 1;
	
	fscanf(f, "%d %d %d %d ", &boxes, &objects, &w, &h);
	
	for(i = 0; i < boxes; i++)
	{
		fgets(buf, 80, f);
		box[i][0] = atoi(buf);
		box[i][1] = atoi(strchr(buf, ' '));
		
		map[ pair<int, int>(box[i][0] / w, box[i][1] / h) ] = i;
	}
	
	for(i = 0; i < objects; i++)
	{
		fgets(buf, 80, f);
		ci = atoi(buf);
		cj = atoi(strchr(buf, ' '));
		
		obj = pair<int, int>(ci / w, cj / h);
		
		for(ai = 0; ai < 2; ai++)
		{
			for(aj = 0; aj < 2; aj++)
			{
				adj = pair<int, int>( obj.first - ai, obj.second - aj );
				
				if(adj.first < 0 || adj.second < 0) continue;
				
				it = map.find(adj);
				
				if(it != map.end())
					if(in_box(ci, cj, (*it).second))
					{
						ans++;
						break;
					}
			}
			
			if(aj != 2) break;
		}
	}
	
	fclose(f);
	f = fopen("ograzi.out", "w");
	if(!f) return 1;
	
	fprintf(f, "%d\n", ans);
	fclose(f);
	return 0;
}

/*
	Read this far?
	http://ascending.wordpress.com/
*/