Cod sursa(job #2059455)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 7 noiembrie 2017 01:19:54
Problema Ograzi Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <bits/stdc++.h>

#define MaxN 312501
#define MOD 20011
#define MOD2 10007
#define MOD3 11927
#define INF 2140000000

using namespace std;

FILE *IN,*OUT;

int N,M,W,H,A,B,Ans=0;
vector<pair<int,int> > Hash[4][MOD];

void Add(int x,int y,int t)
{
    int X=(x-0.5)/W;
    int Y=(y-0.5)/H;
    int S=(1LL*X*MOD2+1LL*Y*MOD3)%MOD;
    Hash[t][S].push_back({x,y});
}
bool Search(int x,int y,int t)
{
    int Q,R,q,r;
    int X=(x-0.5)/W;
    int Y=(y-0.5)/H;
    int S=(1LL*X*MOD2+1LL*Y*MOD3)%MOD;
    for(int i=0;i<Hash[t][S].size();i++)
    {
        q=Hash[t][S][i].first;
        r=Hash[t][S][i].second;
        Q=(q-0.5)/W;
        R=(r-0.5)/H;
        if(X==Q&&Y==R)
        {
            if(t==0)
                return x<=q&&y<=r;
            else if (t==2)
                return x<=q&&y>=r;
            else if(t==1)
                return x>=q&&y<=r;
            else return x>=q&&y>=r;
        }
    }
    return false;
}

int main()
{
    IN=fopen("ograzi.in","r");
    OUT=fopen("ograzi.out","w");

    fscanf(IN,"%d%d%d%d",&N,&M,&W,&H);

    for(int i=1;i<=N;i++)
    {
        fscanf(IN,"%d%d",&A,&B);
        Add(A,B,3);
        Add(A+W,B+H,0);
        Add(A+W,B,2);
        Add(A,B+H,1);
    }

    for(int i=1;i<=M;i++)
    {
        fscanf(IN,"%d%d",&A,&B);
        if(Search(A,B,0)||Search(A,B,1)||Search(A,B,2)||Search(A,B,3))
            Ans++;
    }
    fprintf(OUT,"%d\n",Ans);
    return 0;
}