Pagini recente » Stelele Informaticii 2010, gimnaziu şi clasa a IX-a, ziua 1 | Statistici Odagiu Sebastian (odagiusebi) | Caramele | Statistici Parasca Andrei (andrei_xds) | Cod sursa (job #1469076)
#include <iostream>
#include <fstream>
using namespace std;
int nn;
struct Node {
unsigned int lix, lfx, liy, lfy, c;
Node* ch[4];
Node() {}
Node(unsigned int lix, unsigned int lfx, unsigned int liy, unsigned int lfy, unsigned int c) : lix(lix), lfx(lfx),
liy(liy), lfy(lfy), c(c) { ch[0] = ch[1] = ch[2] = ch[3] = NULL; nn++; }
inline bool has(unsigned int x, unsigned int y) {
return lix <= x && x <= lfx && liy <= y && y <= lfy;
}
inline bool unit() {
return lix == lfx && liy == lfy;
}
};
Node root(0, 4000000000, 0, 4000000000, 0);
Node mem[512 * 20000];
int nextmem = 0;
void split(Node* node) {
for (long long i = 0; i < 4; ++i) {
node->ch[i] = &mem[nextmem];
mem[nextmem] = 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);
nextmem++;
}
}
void add(Node* node, unsigned int x, unsigned int y) {
if (!node->has(x, y)) return;
if (!node->unit()) {
if (node->ch[0] == NULL) split(node);
for (int i = 0; i < 4; ++i) {
add(node->ch[i], x, y);
}
}
node->c++;
}
unsigned int ask(Node* node, unsigned int xi, unsigned int xf, unsigned int yi, unsigned int 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 unsigned intersect 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.
unsigned int sol = 0;
for (int 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");
int n, m;
in >> n;
for (int i = 0; i < n; ++i) {
int x, y;
in >> x >> y;
add(&root, x + 2000000000, y + 2000000000);
}
in >> m;
for (int 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;
}