Cod sursa(job #25012)

Utilizator StTwisterKerekes Felix StTwister Data 4 martie 2007 09:41:07
Problema Ograzi Scor 30
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 2.19 kb
#include <stdio.h>
#include <stdlib.h>

#define MMAX 50001
#define NMAX 100001
#define LGN 18

struct point
{
    int x, y;
} P[NMAX];


int PX[MMAX], PY[MMAX];
int X[NMAX], Y[NMAX];
int T[LGN][NMAX];
int N,M,W,H;
int sol;
int x1,y1,x2,y2;

int cmp(const void *i, const void *j)
{
  return ((point *)i)->x-((point *)j)->x;
}

void build(int lv, int l, int r)
{
    int m = (l + r) >> 1, i, j, k;
    if (l == r)
    {
        T[lv][l] = P[l].y;
        return;
    }
    build(lv+1, l, m), build(lv + 1, m+1, r);
    for (i=l, j=m + 1, k=l; i<=m || j <= r; )
        if (j>r || (i<=m && T[lv+1][i]<T[lv+1][j]))
            T[lv][k++] = T[lv + 1][i++];
        else
            T[lv][k++] = T[lv + 1][j++];
}

int search(int A[], int l, int r, int v)
{
    int p, step;
    if (v < A[l]) return l - 1;
    for (step=1; step<(r-l + 1);step<<= 1);
    for (p = l; step; step >>= 1)
    if (p + step <= r && A[p + step] <= v)
       p += step;
    return p;
}

int query(int lv, int l, int r)
{
    int m, t = 0;
    if (x1 <= l && r <= x2)
    {
       if (y2 < T[lv][l] || y1 > T[lv][r])
          return 0;
       if (y1 < T[lv][l] && T[lv][r] < y2)
          return (r - l + 1);
       t=search(T[lv], l, r, y2) -
         search(T[lv], l, r, y1 - 1);
   }
  else
 {m = (l + r) >> 1;
  if (x1 <= m) t += query(lv + 1, l, m);
  if (x2 > m) t += query(lv + 1, m + 1, r);
  }
  return t;
}

void solve()
{
    sol = 0;
    qsort(P, N, sizeof(point), cmp);
    for (int i = 0; i < N; i++)
        X[i] = P[i].x;
    build(0, 0, N - 1);
    for (int i = 0; i<M; ++i)
    {
        x1 = PX[i];
        y1 = PY[i];
        x2 = PX[i] + W;
        y2 = PY[i] + H;
        x1 = search(X, 0, N - 1, x1 - 1) + 1;
        x2 = search(X, 0, N - 1, x2);
        sol += query(0, 0, N - 1);
    }
}

int main()
{
    freopen("ograzi.in", "r", stdin);
    freopen("ograzi.out", "w", stdout);

    scanf("%d %d %d %d", &M, &N, &W, &H);

    for (int i = 0; i<M; ++i)
    {
        scanf("%d %d", &PX[i], &PY[i]);
    }

    for (int i = 0; i<N; ++i)
    {
        scanf("%d %d", &P[i].x, &P[i].y);
    }

    solve();

    printf("%d\n", sol);
}