Cod sursa(job #1518537)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 5 noiembrie 2015 22:41:44
Problema Ograzi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <array>
#include <cstdio>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <utility>
#include <cstdlib>
using namespace std;
 
template <int dim>
class parsator{
    FILE* f;
	array<char, dim> buf;
    int poz;
    void refresh(){
        if(poz == dim){
            poz = 0;
			fread(&buf[0], 1, dim, f); } }
public:
    parsator(const char* const name): f(fopen(name, "r")), poz(dim){
		refresh(); }
	~parsator(){
		fclose(f); }
    parsator<dim>& operator>>(int& x){
        x = 0;
        while(!isdigit(buf[poz])){
            ++poz;
            refresh(); }
        while(isdigit(buf[poz])){
			x = x*10 + buf[poz] - '0';
            ++poz;
            refresh(); }
        return *this; } };

template <typename T, int dim>
class hash_table{
	array<vector<pair<pair<int, int>, T>>, dim> buf;
public:
	hash_table(){}
	T& operator[](const pair<int, int>& p){
		const size_t hs = ((11*p.first) ^ p.second)%dim;
		for(auto& t : buf[hs]){
			if(t.first == p){
				return t.second; } }
		buf[hs].push_back({});
		buf[hs].back().first = p;
		return buf[hs].back().second; } };
 
bool included(const int w, const int h, const int xdr, const int ydr, const int xp, const int yp){
    return xdr <= xp && ydr <= yp && xp <= xdr+w && yp <= ydr+h; }
 
int main(){
    parsator<3> f("ograzi.in");
	FILE* g = fopen("ograzi.out", "w");
    int n, m, w, h;
    f >> n >> m >> w >> h;
    hash_table<vector<pair<int, int>>, 37139> celule;
    for(int i = 0, x, y; i < n; ++i){
        f >> x >> y;
        const int x_ = x/w, y_ = y/h;
		celule[make_pair(x_, y_)].push_back({x, y}); }

    int rez = 0;
    for(int i = 0, x, y; i < m; ++i){
        f >> x >> y;
		const int x_ = x/w, y_ = y/h;
		for(int dx = -1; dx <= 0; ++dx){
			for(int dy = -1; dy <= 0; ++dy){
				const auto& de_ver = celule[make_pair(x_+dx, y_+dy)];
				for(const auto ograda : de_ver){
					if(included(w, h, ograda.first, ograda.second, x, y)){
						++rez; } } } } }

	fprintf(g, "%d", rez);
	fclose(g);
    return 0; }