Cod sursa(job #942326)

Utilizator SteveStefan Eniceicu Steve Data 21 aprilie 2013 20:35:33
Problema Ograzi Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <fstream>
#include <vector>
#define TR(C, it) for (typeof (C.begin ()) it = C.begin (); it != C.end (); it++)
#define mod 1011
using namespace std;

int N, M, W, H;
pair <int, int> ograzi[50011];
vector <int> map[1015][1015];
int val1[] = {0, -1, 0, -1};
int val2[] = {0, 0, -1, -1};
char pars[17];

int Inside (int x, int y, int i)
{
    int x1 = ograzi[i].first;
    int y1 = ograzi[i].second;
    if (x >= x1 && x <= x1 + W && y >= y1 && y <= y1 + H) return 1;
    return 0;
}

int main ()
{
    ifstream fin ("ograzi.in");
    ofstream fout ("ograzi.out");
    fin >> N >> M >> W >> H;
    fin.getline (pars, 10);
    for (int i = 0; i < N; i++)
    {
        fin.getline (pars, 15);
        int x = 0, y = 0, j;
        for (j = 0; pars[j] >= '0' && pars[j] <= '9'; j++)
            x = x * 10 + pars[j] - '0';
        for (++j; pars[j] >= '0' && pars[j] <= '9'; j++)
            y = y * 10 + pars[j] - '0';
        ograzi[i].first = x;
        ograzi[i].second = y;
        x /= W, y /= H;
        map[(x * 101 + y) % mod][(y * 101 + x) % mod].push_back (i);
    }
    int cnt = 0;
    for (int i = 0; i < M; i++)
    {
        fin.getline (pars, 15);
        int x = 0, y = 0, j;
        for (j = 0; pars[j] >= '0' && pars[j] <= '9'; j++)
            x = x * 10 + pars[j] - '0';
        for (++j; pars[j] >= '0' && pars[j] <= '9'; j++)
            y = y * 10 + pars[j] - '0';
        int good = 0;
        for (int j = 0; j < 4; j++)
            if (!good)
            {
                int alfa = x / W + val1[j], beta = y / H + val2[j];
                if (alfa >= 0 && beta >= 0)
                    TR (map[(alfa * 101 + beta) % mod][(beta * 101 + alfa) % mod], it)
                        if (Inside (x, y, *it)) good = 1;
            }
        cnt += good;
    }
    fout << cnt;
    fout.close ();
    return 0;
}