Cod sursa(job #984334)

Utilizator stefanzzzStefan Popa stefanzzz Data 14 august 2013 10:42:34
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
#include <vector>
#define NRM 104743
#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,p;
char s[MAXS];
bool gata;
vector<int> v[NRM];

int getnr();
int valhash(int x,int y);

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();
        gata=0;
        for(j=0;j<4&&!gata;j++){
            xx=x/w+dirx[j];
            yy=y/h+diry[j];
            if(xx<0||yy<0)
                continue;
            a=valhash(xx,yy);
            for(k=0;k<v[a].size()&&!gata;k++){
                p=v[a][k];
                if(x>=xd[p]&&x<=xd[p]+w&&y>=yd[p]&&y<=yd[p]+h){
                    gata=1;
                    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 (951161LL*x+y)%NRM;}