Cod sursa(job #769614)

Utilizator badmanDragan Dan badman Data 20 iulie 2012 10:53:14
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <stdio.h>

#define mod 131071
#define max 50010

using namespace std;

struct pct {
    long x, y;
};

FILE *input, *output;
long hash[mod][10], line[mod];
char buf[40];
int n, m, w, h, nc;
long i, j, k, pos, nr, p1, p2;
pct dr[max], p, q;

inline int get_int() {
	int rez = 0;

	while(buf[nc] >= '0' && buf[nc] <= '9')
		rez = rez * 10 + buf[nc++] - '0';

	return rez;
}

void hash_fct(long x, long y)
{
    long p1, p2, sol;
    p1 = x / w;
    p2 = y / h;
    if(x % w == 0)
        p1--;
    if(y % h == 0)
        p2--;
    sol = (p1 * 103 + p2) % mod;
    hash[sol][++line[sol]] = i;
}

void read() {

    input = fopen("ograzi.in", "r");
    fscanf(input, "%d %d %d %d\n", &n, &m, &w, &h);
    for(i = 1; i <= n; i++) {
        fgets(buf, 40, input);
        nc = 0;
        dr[i].x = get_int();
        ++nc;
        dr[i].y = get_int();
        dr[i].x++;
        dr[i].y++;
        hash_fct(dr[i].x, dr[i].y);
        hash_fct(dr[i].x + w, dr[i].y);
        hash_fct(dr[i].x, dr[i].y + h);
        hash_fct(dr[i].x + w, dr[i].y + h);
    }
    for(i = 1; i <= m; i++) {
        fgets(buf, 40, input);
        nc = 0;
        p.x = get_int();
        ++nc;
        p.y = get_int();
        p.x++;
        p.y++;
        p1 = p.x / w;
        p2 = p.y / h;
        if(p.x % w == 0)
            p1--;
        if(p.y % h == 0)
            p2--;
        pos = (p1 * 103 + p2) % mod;

        for(j = 1; j <= line[pos]; j++) {
            q = dr[hash[pos][j]];
            if(q.x <= p.x && p.x <= q.x + w && q.y <= p.y && p.y <= q.y + h) {
                nr++;
                break;
            }
        }
    }
    fclose(input);
}

int main() {

    read();
    output = fopen("ograzi.out", "w");
    fprintf(output, "%ld\n", nr);
    fclose(output);

    return 0;
}