Cod sursa(job #1518587)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 5 noiembrie 2015 23:43:09
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <utility>
#include <cstdlib>
using namespace std;
   
template <int dim>
class parsator{
    ifstream f;
    char buf[dim];
    int poz;
    void refresh(){
        if(poz == dim){
            poz = 0;
            f.read(&buf[0], dim); } }
public:
    parsator(const char* const name): f(name), poz(0){
        f.read(&buf[0], dim); }
    parsator<dim>& operator>>(int& x){
        x = 0;
        while(!isdigit(buf[poz])){
            ++poz;
            refresh(); }
        while(isdigit(buf[poz])){
            x *= 10;
            x += buf[poz] - '0';
            ++poz;
            refresh(); }
        return *this; } };
  
int my_hash(const int a, const int b){
    return (12*a ^ b); }
 
template <int dim>
class hash_table{
    array<vector<pair<int, int> >, dim> buf;
public:
    hash_table(){}
    void add(const int key_x, const int key_y, const int x, const int y){
        const int hs = my_hash(key_x, key_y)%dim;
        buf[hs].emplace_back(x, y); }
    pair<int, int> find(const int w, const int h, const int key_x, const int key_y){
        const int hs = my_hash(key_x, key_y)%dim;
 
        for(const auto& t : buf[hs]){
            if(t.first/w == key_x && t.second/h == key_y){
                return t; } }
        return {-w, -h}; } };
   
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<1000000> f("ograzi.in");
    ofstream g("ograzi.out");
    int n, m, w, h;
    f >> n >> m >> w >> h;
    hash_table<37139> celule;
    for(int i = 0, x, y; i < n; ++i){
        f >> x >> y;
        x += w, y+=h;
        const int x_ = x/w, y_ = y/h;
        celule.add(x_, y_, x, y); }
  
    int rez = 0;
    for(int i = 0, x, y; i < m; ++i){
        f >> x >> y;
        x += w, y+=h;
 
        const int x_ = x/w, y_ = y/h;
        bool is_in = false;
        for(int dx = -1; dx <= 0; ++dx){
            for(int dy = -1; dy <= 0; ++dy){
                const auto ograda = celule.find(w, h, x_+dx, y_+dy);
                if(included(w, h, ograda.first, ograda.second, x, y)){
                    is_in = true; } } }
        if(is_in){
            ++rez; } }
  
    g << rez;
    return 0; }