Pagini recente » Cod sursa (job #2592998) | Cod sursa (job #879794) | Cod sursa (job #2519259) | Cod sursa (job #1418403) | Cod sursa (job #1518284)
#include <fstream>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <tuple>
#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; } };
using ograda = tuple<int, int>;
using oaie = tuple<int, int>;
using nume_celula = tuple<int, int>;
using info_celula = tuple<vector<int>, vector<int> >;
struct celula_hash : public unary_function<nume_celula, size_t>{
size_t operator()(const nume_celula& n)const{
return (hash<int>()(get<0>(n))<<4 + 23) ^ (hash<int>()(get<1>(n))>>1 + 13); } };
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;
unordered_map<nume_celula, info_celula, celula_hash> celule;
celule.reserve(n+m);
vector<tuple<int, int> > ograzi(n), oi(m);
for(int i = 0, x, y; i < n; ++i){
f >> x >> y;
ograzi[i] = tuple<int, int>(x, y);
const int x_ = x/w, y_ = y/h;
for(int dx = 0; dx <= 1; ++dx){
for(int dy = 0; dy <= 1; ++dy){
get<0>(celule[tuple<int, int>(x_+dx, y_+dy)]).push_back(i); } } }
for(int i = 0, x, y; i < m; ++i){
f >> x >> y;
oi[i] = tuple<int, int>(x, y);
get<1>(celule[tuple<int, int>(x/w, y/h)]).push_back(i); }
int rez = 0;
for(const auto& c : celule){
const auto& info = get<1>(c);
for(const auto ograda : get<0>(info)){
for(const auto oaie : get<1>(info)){
//cout << ograda << ' ' << oaie << ' ';
if(included(w, h, get<0>(ograzi[ograda]), get<1>(ograzi[ograda]),
get<0>(oi[oaie]), get<1>(oi[oaie]))){
//cout << '*';
++rez; }
//cout << endl;
} } }
g << rez;
return 0; }