# Cod sursa(job #1468736)

Utilizator Data 6 august 2015 21:01:25 Zoo 40 cpp done Arhiva de probleme 2.34 kb
``````#include <iostream>
#include <fstream>

using namespace std;

int nn;

struct Node {
long long lix, lfx, liy, lfy, c;
Node* ch[4];

Node() : lix(0), lfx(4000000000), liy(0), lfy(4000000000),
c(0) { ch[0] = ch[1] = ch[2] = ch[3] = NULL; }
Node(long long lix, long long lfx, long long liy, long long lfy, long long c) : lix(lix), lfx(lfx),
liy(liy), lfy(lfy), c(c) { ch[0] = ch[1] = ch[2] = ch[3] = NULL; nn++; }

inline bool has(long long x, long long y) {
return lix <= x && x <= lfx && liy <= y && y <= lfy;
}

inline bool unit() {
return lix == lfx && liy == lfy;
}
};

Node root;

void split(Node* node) {
for (long long i = 0; i < 4; ++i) {
node->ch[i] =
new Node(
(i % 2 == 0 ? node->lix : ((node->lix + node->lfx) / 2) + 1),
(i % 2 == 0 ? (node->lix + node->lfx) / 2 : node->lfx),
(i / 2 == 0 ? node->liy : ((node->liy + node->lfy) / 2) + 1),
(i / 2 == 0 ? (node->liy + node->lfy) / 2 : node->lfy),
node->c);
}
}

void add(Node* node, long long x, long long y) {
if (!node->has(x, y)) return;
if (!node->unit()) {
if (node->ch[0] == NULL) split(node);
for (long long i = 0; i < 4; ++i) {
}
}
node->c++;
}

long long ask(Node* node, long long xi, long long xf, long long yi, long long yf) {
if (node == NULL || node->c == 0) return 0;

// Fully contains this node.
if (xi <= node->lix && node->lfx <= xf && yi <= node->liy && node->lfy <= yf)
return node->c;

// Does not even long longersect with this node.
if (xf < node->lix || node->lfx < xi || yf < node->liy || node->lfy < yi)
return 0;

// Intersects with the node, but does not contain it. Distribute to children.
long long sol = 0;
for (long long i = 0; i < 4; ++i) {
sol += ask(node->ch[i], xi, xf, yi, yf);
}

return sol;
}

int main()
{
ifstream in("zoo.in");
ofstream out("zoo.out");
long long n, m, xi, xf, yi, yf;
in >> n;
for (long long i = 0; i < n; ++i) {
long long x, y;
in >> x >> y;
add(&root, x + 2000000000, y + 2000000000);
}
in >> m;
for (long long i = 0; i < m; ++i) {
long long xi, xf, yi, yf;
in >> xi >> yi >> xf >> yf;
out << ask(&root, xi + 2000000000, xf + 2000000000, yi + 2000000000, yf +
2000000000) << "\n";
}

in.close();
out.close();

return 0;
}
``````