Cod sursa(job #2059462)

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

#define MaxN 312501
#define MAX 131072
#define MOD 8009
#define INF 2140000000

using namespace std;

FILE *IN,*OUT;

int N,M,W,H,A,B,Ans=0,X,Y,S,Q,R,r,q,pos=0;
char f[MAX];
vector<pair<int,int> > Hash[4][MOD];

void Add(int x,int y,int t)
{
    X=(x-0.5)/W;
    Y=(y-0.5)/H;
    S=(1048576LL*X+Y)%MOD;
    Hash[t][S].push_back({x,y});
}
bool Search(int x,int y,int t)
{
    X=(x-0.5)/W;
    Y=(y-0.5)/H;
    S=(1048576LL*X+Y)%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;
}
inline void Read(int &nr)
{
    nr=0;
    while(f[pos]<'0'||f[pos]>'9')
    {
        pos++;
        if(pos==MAX)
            fread(f,MAX,1,IN),pos=0;
    }
    while(f[pos]>='0'&&f[pos]<='9')
    {
        nr=10*nr+f[pos++]-'0';
        if(pos==MAX)
            fread(f,MAX,1,IN),pos=0;
    }
}
int main()
{
    IN=fopen("ograzi.in","r");
    OUT=fopen("ograzi.out","w");
    fread(f,1,MAX,IN);

    Read(N);
    Read(M);
    Read(W);
    Read(H);

    for(int i=1;i<=N;i++)
    {
        Read(A);
        Read(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++)
    {
        Read(A);
        Read(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;
}