Cod sursa(job #1469076)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 7 august 2015 15:52:11
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#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;
}