Cod sursa(job #1328611)

Utilizator SmarandaMaria Pandele Smaranda Data 28 ianuarie 2015 16:37:54
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.35 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int M = 100003, N = 16003;
int n, m, c, u, d, a, b;
int aib [4 * M + N];
int G [M][5], Y1 [4 * M + N], Y [4 * M + N];

struct Point {
    int x, y, gr, t;
};

class MyComp {
    public :
        bool operator () (const Point &A, const Point &B) {
            return (A.x < B.x || (A.x == B.x && A.y < B.y));
        }
};

int binarySearch (const int &value) {
    int i, step;

    for (i = 0, step = (1 << 19); step; step >>= 1)
        if (i + step <= d && Y [i + step] <= value)
            i += step;
    return i;
}

int verif (const Point &A, const int X, const int Y) {
    if (A.x == X && A.y == Y)
        return A.t;
    return 0;
}

inline int lsb (int x) {
    return x & (-x);
}

void update (int i, const int &value) {
    for (; i <= d; i = i + lsb (i))
        aib [i] += value;
}

int query (int i) {
    int ans = 0;

    for (; i >= 1; i = i - lsb (i))
        ans += aib [i];
    return ans;
}

Point P [4 * M + N];


int main () {
    int i, x1, x2, y1, y2, ans;

    freopen ("zoo.in", "r", stdin);
    freopen ("zoo.out", "w", stdout);

    scanf ("%d", &n);
    for (i = 1; i <= n; i ++) {
        scanf ("%d%d", &P [i].x, &P [i].y);
        Y1 [i] = P [i].y;
    }
    u = c = n;
    scanf ("%d", &m);
    for (i = 1; i <= m; i ++) {
        scanf ("%d%d%d%d", &x1, &y1, &x2, &y2);
        P [++ u].x = x1 - 1;
        P [u].y = y1 - 1;
        P [u].gr = i;

        P [++ u].x = x1 - 1;
        P [u].y = y2;
        P [u].gr = i;

        P [++ u].x = x2;
        P [u].y = y1 - 1;
        P [u].gr = i;

        P [++ u].x = x2;
        P [u].y = y2;
        P [u].gr = i;

        Y1 [++ c] = y1;
        Y1 [++ c] = y2;
    }
    sort (P + 1, P + 1 + u, MyComp ());
    sort (Y1 + 1, Y1 + 1 + c);
    Y1 [c + 1] = Y1 [c] - 10;
    for (i = 1; i <= c; i ++)
        if (Y1 [i] != Y1 [i + 1])
            Y [++ d] = Y1 [i];
    for (i = 1; i <= u; i ++) {
        if (P [i].gr) {
            G [P [i].gr][++ G [P [i].gr][0]] = i;
        }
        P [i].y = binarySearch (P [i].y);
    }
    for (i = 1; i <= u; i ++)
        if (P [i].gr == 0)
            update (P [i].y, 1);
        else
            P [i].t = query (P [i].y);
    for (i = 1; i <= m; i ++) {
        a = G [i][1];
        b = G [i][2];
        c = G [i][3];
        d = G [i][4];
        ans = 0;
        x1 = min (min (min (P [a].x, P [b].x), P [c].x), P [d].x);
        y1 = min (min (min (P [a].y, P [b].y), P [c].y), P [d].y);
        x2 = max (max (max (P [a].x, P [b].x), P [c].x), P [d].x);
        y2 = max (max (max (P [a].y, P [b].y), P [c].y), P [d].y);
        ans += verif (P [a], x2, y2);
        ans += verif (P [b], x2, y2);
        ans += verif (P [c], x2, y2);
        ans += verif (P [d], x2, y2);

        ans -= verif (P [a], x1, y2);
        ans -= verif (P [b], x1, y2);
        ans -= verif (P [c], x1, y2);
        ans -= verif (P [d], x1, y2);

        ans -= verif (P [a], x2, y1);
        ans -= verif (P [b], x2, y1);
        ans -= verif (P [c], x2, y1);
        ans -= verif (P [d], x2, y1);

        ans += verif (P [a], x1, y1);
        ans += verif (P [b], x1, y1);
        ans += verif (P [c], x1, y1);
        ans += verif (P [d], x1, y1);
        printf ("%d\n", ans);
    }
    return 0;
}