Cod sursa(job #2059466)

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

#define MaxN 50005
#define MAX 131072
#define MOD 131071
#define INF 2140000000

using namespace std;

FILE *IN,*OUT;

int N,M,W,H,A,B,Ans=0,pos=0,X,Y;
char f[MAX];
pair<int,int>v[MaxN];
vector<pair<long long,int> >Hash[MOD];
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;
    }
}
bool check(int x,int y,int p)
{
    return x>=v[p].first&&y>=v[p].second&&x<=v[p].first+W&&y<=v[p].second+H;
}
void Add(int x,int y,int p)
{
    X=(x-0.5)/W;
    Y=(y-0.5)/H;
    long long S=((1LL*X<<30)+Y)%MOD;
    Hash[S%MOD].push_back({S,p});
}
bool Search(int x,int y,int type)
{
    X=(x-0.5)/W;
    X-=type&1;
    Y=(y-0.5)/H;
    Y-=(type>>1)&1;
    if(X<0||Y<0)
        return false;
    long long S=((1LL*X<<30)+Y)%MOD;
    int s=S%MOD;
    for(int i=0;i<Hash[s].size();i++)
        if(S==Hash[s][i].first)
            return check(x,y,Hash[s][i].second);
    return false;
}
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);
        v[i]={A,B};
        Add(A,B,i);
    }

    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;
}