Cod sursa(job #2095197)

Utilizator refugiatBoni Daniel Stefan refugiat Data 27 decembrie 2017 10:24:01
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#define MAXN 50005
#define MAX 131072
#define MOD 131071
#define IF 2140000000
using namespace std;

FILE *si=fopen("ograzi.in","r");
FILE *so=fopen("ograzi.out","w");
int n,m,w,h,a,b,ans=0,pos=0,nx,ny;
char f[MAX];
pair<int,int>v[MAXN];
vector<pair<long long,int> >myhash[MOD];
inline void read(int &nr)
{
    nr=0;
    while(f[pos]<'0'||f[pos]>'9')
    {
        pos++;
        if(pos==MAX)
            fread(f,MAX,1,si),pos=0;
    }
    while(f[pos]>='0'&&f[pos]<='9')
    {
        nr=10*nr+f[pos++]-'0';
        if(pos==MAX)
            fread(f,MAX,1,si),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)
{
    nx=(x-0.5)/w;
    ny=(y-0.5)/h;
    long long s=(1LL*nx<<30)+ny;
    myhash[s%MOD].push_back({s,p});
}
bool caut(int x,int y,int tip)
{
    nx=(x-0.5)/w;
    nx-=tip&1;
    ny=(y-0.5)/h;
    ny-=(tip>>1)&1;
    if(nx<0||ny<0)
        return false;
    long long sum=(1LL*nx<<30)+ny;
    int s=sum%MOD;
    for(int i=0;i<myhash[s].size();i++)
        if(sum==myhash[s][i].first)
            return check(x,y,myhash[s][i].second);
    return false;
}
int main()
{
    fread(f,1,MAX,si);

    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(caut(a,b,0)||caut(a,b,1)||caut(a,b,2)||caut(a,b,3))
            ans++;
    }
    fprintf(so,"%d\n",ans);
    return 0;
}