Cod sursa(job #2952410)

Utilizator lolismekAlex Jerpelea lolismek Data 9 decembrie 2022 10:16:44
Problema Ograzi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <map>

using namespace std;

ofstream fout("ograzi.out");

class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;

	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}
	
	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
	
	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};

const int NMAX = 1e5;

const int BASE = 29;
const int MOD = 666013;

int n, m, w, h;

struct Rect{
    int x1, y1;
    int x2, y2;
}rects[NMAX + 1];

bool inside(pair <int, int> p, Rect rect){
    return (rect.x1 <= p.first && p.first <= rect.x2 && rect.y2 <= p.second && p.second <= rect.y1);
}

int HashPair(pair <int, int> p){
    return (1ll * BASE * p.first + p.second) % MOD;
}

vector <pair <int, int>> mp[MOD + 1];

int main(){

    InParser fin("ograzi.in");

    fin >> n >> m >> w >> h;

    for(int i = 1; i <= n; i++){
        fin >> rects[i].x1 >> rects[i].y2;
        rects[i].y1 = rects[i].y2 + h;
        rects[i].x2 = rects[i].x1 + w;
    }

    for(int i = 1; i <= m; i++){
        int x, y;
        fin >> x >> y;

        mp[HashPair({x / w, y / h})].push_back({x, y});
    }   

    int ans = 0;

    for(int i = 1; i <= n; i++){
        int quadrant1 = HashPair({rects[i].x1 / w, rects[i].y1 / h});
        int quadrant2 = HashPair({rects[i].x2 / w, rects[i].y1 / h});
        int quadrant3 = HashPair({rects[i].x2 / w, rects[i].y2 / h});
        int quadrant4 = HashPair({rects[i].x1 / w, rects[i].y2 / h});

        for(auto p : mp[quadrant1]){
            if(inside(p, rects[i]))
                ans++;
        }

        for(auto p : mp[quadrant2]){
            if(inside(p, rects[i]))
                ans++;
        }

        for(auto p : mp[quadrant3]){
            if(inside(p, rects[i]))
                ans++;
        }

        for(auto p : mp[quadrant4]){
            if(inside(p, rects[i]))
                ans++;
        }
    }

    fout << ans << '\n';

    return 0;
}