Cod sursa(job #826529)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 30 noiembrie 2012 20:48:57
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.4 kb
#include <fstream>
#include <cstdlib>
#include <algorithm>
#define MAX_SIZE 16001

using namespace std;

ifstream input("zoo.in");
ofstream output("zoo.out");



typedef struct
{
    int x_bot;
    int y_bot;
    int x_top;
    int y_top;
}dreptunghi;

typedef struct
{
    int x;
    int y;
}coordonata;

dreptunghi tree[MAX_SIZE * 3];
coordonata vect[MAX_SIZE];

bool cmp(coordonata a , coordonata b)
{
    if ( a . x != b . x)
    {
        return a.x < b.x;
    }
    else
    {
        return a.y < b.y;
    }
}

int minim(int a ,int b)
{
    if (a < b) return a;
    else return b;
}
int maxim(int a , int b)
{
    if (a > b) return a;
    else return b;
}

char included(dreptunghi a , dreptunghi b) // a  inclus in b ?
{
    return (a.x_bot >= b.x_bot && a.y_bot >= b.y_bot && a.x_top <= b.x_top && a.y_top <= b.y_top);
}

char intersect(dreptunghi a , dreptunghi b)
{
    int colt1_x = minim(a.x_bot,a.x_top);
    int colt1_y = maxim(a.y_bot,a.y_top);
    int colt2_x = maxim(a.x_bot,a.x_top);
    int colt2_y = minim(a.y_bot,a.y_top);
    if (colt1_x <= b.x_top && colt1_x >= b.x_bot && colt1_y <= b.y_top && colt1_y >= b.y_bot)
    {
        return 1;
    }
    if (colt2_x <= b.x_top && colt2_x >= b.x_bot && colt2_y <= b.y_top && colt2_y >= b.y_bot)
    {
        return 1;
    }
    if (a.x_bot <= b.x_top && a.x_bot >= b.x_bot && a.y_bot <= b.y_top && a.y_bot >= b.y_bot)
    {
        return 1;
    }
    if (a.x_top <= b.x_top && a.x_top >= b.x_bot && a.y_top <= b.y_top && a.y_top >= b.y_bot)
    {
        return 1;
    }
    return 0;
}

int puncte = 0;

void query_tree(int nod , dreptunghi value , int left , int right)
{

    if (intersect(tree[nod],value) == 1)
    {
        if (included(tree[nod],value) == 1)
        {
            puncte += right - left + 1;
            return;
        }
        int middle = (left + right) / 2;
        query_tree(2*nod , value , left , middle);
        query_tree(2*nod+1 , value , middle+1 , right);

    }
    else
    {
        return;
    }

}

void update_tree(int nod , dreptunghi value , int poz_vect , int left , int right)
{
    if (left == right)
    {
        tree[nod] = value;
        return;
    }

    int middle = (left + right) >> 1;

    if (poz_vect <= middle) update_tree(2*nod , value , poz_vect , left , middle);
    else update_tree(2 * nod +1 , value , poz_vect , middle + 1 , right);

    tree[nod].x_bot =  minim(tree[2*nod].x_bot , tree[2*nod+1].x_bot);
    tree[nod].y_bot =  minim(tree[2*nod].y_bot , tree[2*nod+1].y_bot);
    tree[nod].x_top =  maxim(tree[2*nod].x_top , tree[2*nod+1].x_top);
    tree[nod].y_top =  maxim(tree[2*nod].y_top , tree[2*nod+1].y_top);
}

int main()
{
    int N , M;
    input >> N;
    for (int i = 1; i <= N ; i++)
    {

            input >> vect[i].x >> vect[i].y;

    }
    sort(vect,vect+N+1,cmp);
    for (int i = 1 ; i <= N; i++)
    {
        dreptunghi t;
        t.x_bot = vect[i].x;
        t.x_top = vect[i].x;
        t.y_bot = vect[i].y;
        t.y_top = vect[i].y;
        update_tree(1,t,i,1,N);
    }
    input >> M;
    for (int i = 1 ; i <= M;i++)
    {
        dreptunghi t;
        input >> t.x_bot >> t.y_bot >> t.x_top >> t.y_top;
        puncte = 0;
        query_tree(1,t,1,N);
        output << puncte << "\n";
    }
    input.close();
    output.close();
    return 0;
}