Cod sursa(job #984332)

Utilizator stefanzzzStefan Popa stefanzzz Data 14 august 2013 10:32:41
Problema Ograzi Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
#include <vector>
#define MAXCORD 1000005
#define NRM 951161
#define MAXS 25
#define MAXN 50005
using namespace std;
ifstream f("ograzi.in");
ofstream g("ograzi.out");

int n,m,w,h,dirx[4]={0,-1,0,-1},diry[4]={0,0,-1,-1},xd[MAXN],yd[MAXN],xx,yy,sol,a,cnt,x,y;
char s[MAXS];
vector<int> v[MAXCORD];

int getnr();
int valhash(int x,int y);
bool inclus(int p);

int main()
{
    int i,j,k;
    f>>n>>m>>w>>h;
    f.getline(s,MAXS,'\n');
    for(i=1;i<=n;i++){
        f.getline(s,MAXS,'\n');
        cnt=0;
        xd[i]=getnr();
        yd[i]=getnr();
        v[valhash(xd[i]/w,yd[i]/h)].push_back(i);}
    for(i=1;i<=m;i++){
        f.getline(s,MAXS,'\n');
        cnt=0;
        x=getnr();
        y=getnr();
        for(j=0;j<4;j++){
            xx=x/w+dirx[j];
            yy=y/h+diry[j];
            a=valhash(xx,yy);
            for(k=0;k<v[a].size();k++)
                if(inclus(v[a][k]))
                    sol++;}}
    g<<sol;
    f.close();
    g.close();
    return 0;
}

int getnr(){
    int a=0;
    while(s[cnt]>='0'&&s[cnt]<='9')
        a=a*10+s[cnt++]-'0';
    cnt++;
    return a+1;}

int valhash(int x,int y){
    return (1LL*x*478637+y)%NRM;}

bool inclus(int p){
    if(x>=xd[p]&&x<=xd[p]+w&&y>=yd[p]&&y<=yd[p]+h)
        return 1;
    return 0;}