Cod sursa(job #1515271)

Utilizator preda.andreiPreda Andrei preda.andrei Data 1 noiembrie 2015 13:13:08
Problema Zoo Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <iostream>
#include <stdio.h>
#include <cmath>

using namespace std;

struct Pozitie{
    int x, y;
};

Pozitie poz[16001];

int cautare(int n, int x, int y){
    int st, dr, mij, p=0;

    st=1;
    dr=n;
    while(st<=dr){
        mij=st+(dr-st)/2;
        if(poz[mij].x>=x && poz[mij].y>=y){
            p=mij;
            dr=mij-1;
        }
        else st=mij+1;
    }

    return p;
}

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

    Pozitie paux;
    int x, y, x2, y2;
    int n, m, p, pct, st;

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

    for(int i=1; i<n; ++i){
        p=i;
        for(int j=i+1; j<=n; ++j)
            if(poz[j].x<poz[p].x || (poz[j].x==poz[p].x && poz[j].y<poz[p].y))
                p=j;
        if(p!=i){
            paux=poz[i];
            poz[i]=poz[p];
            poz[p]=paux;
        }
    }

    fscanf(fin, "%d", &m);
    for(int i=1; i<=m; ++i){
        fscanf(fin, "%d%d%d%d", &x, &y, &x2, &y2);
        st=cautare(n, x, y);
        pct=0;
        while(st<=n && poz[st].x<=x2){
            if(poz[st].y>=y && poz[st].y<=y2)
                pct++;
            st++;
        }

        fprintf(fout, "%d\n", pct);

    }

    /*for(int i=1; i<=n; ++i){
        fprintf(fout, "%d %d\n", poz[i].x, poz[i].y);
    }*/

    return 0;
}