Cod sursa(job #29920)

Utilizator mariusdrgdragus marius mariusdrg Data 11 martie 2007 19:21:05
Problema Ograzi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.87 kb
#include <stdio.h>
#include<string.h>
#include <vector>

using namespace std;

const int maxn = 254312;
const int maxn1 =  50001;
const int maxn2 = 100001;

int i, j, hs;
int x[maxn1];
int x2;
int hl;
int y2;
char s1[maxn1];
int pr;
int y[maxn1];
int ox[maxn2];
int oy[maxn2];
int n;
int m;
int nr;
int w;

vector <int> vect[maxn];

int hash(int a,int b)
{
        int h = 0;
        h ^= (h << 5) + (h >> 2) + a;
        h ^= (h << 5) + (h >> 2) + b;
        return h % maxn;

}

int main()
{
        hl = 0;
        freopen("ograzi.in","r",stdin);
        freopen("ograzi.out","w",stdout);
        hs = 0;
        scanf(" %d %d %d %d ",&n,&m,&w,&hs);
        for(i = 1;i <= n; ++i)
        {
                fgets(s1,100,stdin);
                j = 0;
                pr = 0;
                while(s1[j] != ' ')
                {
                        pr *= 10;
                        pr += s1[j] - '0';
                        ++j;
                }
                ++j;
                x[i] = pr;
                pr = 0;
                while(s1[j] != '\n')
                {
                        pr *= 10;
                        pr += s1[j] - '0';
                        ++j;
                }
                y[i] = pr;
        }
        for(i = 1;i <= m; ++i)
        {
                fgets(s1,100,stdin);
                j = 0;
                pr = 0;
                while(s1[j] != ' ')
                {
                        pr *= 10;
                        pr += s1[j] - '0';
                        ++j;
                }
                ++j;
                ox[i] = pr;
                pr = 0;
                while(s1[j] != '\n')
                {
                        pr *= 10;
                        pr += s1[j] - '0';
                        ++j;
                }
                oy[i] = pr;

                hl = hash(ox[i]/w,oy[i]/hs);
                vect[hash(ox[i]/w,oy[i]/hs)].push_back(i);
        }
/*        for(i = 1;i <= n; ++i)
        {
                vector <int>:: iterator it;
                hl = hash(x[i] / w, y[i] / hs);
                m = vect[hl].size() - 1;
                for(j = 0, it = vect[hl].begin(); it != vect[hl].end()&& j <= m; ++it, ++j)
                {
                        x2 = ox[*it];
                        y2 = oy[*it];
                        if (x[i] <= ox[*it] && x[i]+w >= ox[*it] && y[i] <= oy[*it] && oy[*it] <= y[i] + hs)
                        {
                                nr++;
                                vect[hl][j] = vect[hl][m];
                                vect[hl].pop_back();
                                m--;
                                --j;
                                --it;
                        }
                 }
                 hl = hash(x[i] / w + 1, y[i] / hs);
                 m = vect[hl].size() - 1;
                 for(j = 0,it = vect[hl].begin(); it != vect[hl].end() && j <= m; ++it, ++j)
                 {
                         x2 = ox[*it];
                        y2 = oy[*it];
                        if (x[i] <= ox[*it] && x[i]+w >= ox[*it] && y[i] <= oy[*it] && oy[*it] <= y[i] + hs)
                        {
                                nr++;
                                vect[hl][j] = vect[hl][m];
                                vect[hl].pop_back();
                                m--;
                                 --j;
                                --it;
                        }
                 }
                 hl = hash(x[i] / w, y[i] / hs + 1);
                 m = vect[hl].size() - 1;
                 for(j = 0,it = vect[hl].begin(); it != vect[hl].end()&& j <= m; ++it, ++j)
                 {
                         x2 = ox[*it];
                        y2 = oy[*it];
                        if (x[i] <= ox[*it] && x[i]+w >= ox[*it] && y[i] <= oy[*it] && oy[*it] <= y[i] + hs)
                        {
                                nr++;
                                vect[hl][j] = vect[hl][m];
                                vect[hl].pop_back();
                                m--;
                                 --j;
                                --it;
                        }
                 }
                 hl = hash(x[i] / w + 1,y[i] / hs + 1);
                 m = vect[hl].size() - 1;
                 for(j = 0, it = vect[hl].begin(); it != vect[hl].end()&& j <= m; ++it, ++j)
                 {
                        x2 = ox[*it];
                        y2 = oy[*it];
                        if (x[i] <= ox[*it] && x[i]+w >= ox[*it] && y[i] <= oy[*it] && oy[*it] <= y[i] + hs)
                        {
                                nr++;
                                vect[hl][j] = vect[hl][m];
                                vect[hl].pop_back();
                                m--;
                                --j;
                                --it;
                        }
                 }
        }
        printf("%d\n",nr);
  */
        return 0;
}