Cod sursa(job #1596352)

Utilizator preda.andreiPreda Andrei preda.andrei Data 10 februarie 2016 22:20:47
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 kb
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

struct Pozitie{
    int x, y;
};

Pozitie pozitii[16001];

int cauta(Pozitie p, int n);
int cmpPozitii(Pozitie p1, Pozitie p2);
int partitionare(int st, int dr);
void quicksort(int st, int dr);
void interschimba(Pozitie &p1, Pozitie &p2);

int main()
{
    FILE *fin = fopen("zoo.in", "r");
    FILE *fout = fopen("zoo.out", "w");

    int n, m, x, y, x2, y2, ind1, ind2, k;

    fscanf(fin, "%d", &n);
    for(int i=1; i<=n; ++i)
        fscanf(fin, "%d%d", &pozitii[i].x, &pozitii[i].y);

    fscanf(fin, "%d", &m);
    for(int i=1; i<=m; ++i){
        fscanf(fin, "%d%d%d%d", &x, &y, &x2, &y2);

        ind1 = cauta((Pozitie) {x, y}, n);
        ind2 = cauta((Pozitie) {x2, y2}, n);

        k = 0;
        //fprintf(fout, "ind1 = %d   ind2 = %d\n", ind1, ind2);
        for(int j=ind1; j<=ind2; ++j)
            if(pozitii[j].x >= x && pozitii[j].x <= x2 &&
                pozitii[j].y >= y && pozitii[j].y <= y2)
                k++;
        fprintf(fout, "%d\n", k);
    }

    return 0;
}

int partitionare(int st, int dr){
    Pozitie pivot;
    int i, j;

    pivot = pozitii[st + (dr - st) / 2];
    interschimba(pozitii[st], pozitii[st + (dr - st) / 2]);
    i = st + 1;
    j = dr;

    while(i <= j){
        while(i <= j && cmpPozitii(pivot, pozitii[i]) >= 0)
            i++;
        while(i <= j && cmpPozitii(pivot, pozitii[j]) < 0)
            j--;
        if(i <= j){
            interschimba(pozitii[i], pozitii[j]);
            i++;
            j--;
        }
    }
    i--;
    interschimba(pozitii[i], pozitii[st]);

    return i;
}

void quicksort(int st, int dr){
    if(st >= dr)
        return;
    int poz = partitionare(st, dr);
    quicksort(st, poz - 1);
    quicksort(poz + 1, dr);
}

int cauta(Pozitie p, int n){
    int st = 1, dr = n, mij, rez;

    while(st <= dr){
        mij = st + (dr - st) / 2;
        rez = cmpPozitii(p, pozitii[mij]);
        if(rez == 0)
            return mij;
        else if(rez > 0)
            st = mij + 1;
        else dr = mij - 1;
    }
    if(dr <= 0)
        dr++;
    return dr;
}

int cmpPozitii(Pozitie p1, Pozitie p2){
    if(p1.x < p2.x)
        return -1;
    if(p1.x > p2.x)
        return 1;
    if(p1.y < p2.y)
        return -1;
    if(p1.y > p2.y)
        return 1;
    return 0;
}

void interschimba(Pozitie &p1, Pozitie &p2){
    Pozitie paux = p1;
    p1 = p2;
    p2 = paux;
}