Cod sursa(job #25429)

Utilizator MARCELMIHALCEA MARICEL MARCEL Data 4 martie 2007 12:34:55
Problema Ograzi Scor 20
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 1.79 kb

#include<stdio.h>
#include<stdlib.h>

#define MaxC 1000001
#define Nmax 5001
#define Mmax 10001


int arb[2*MaxC];

struct events {
 long x,y;
 char c;
  } d[2*Nmax+Mmax+1];

  long n,m,w,h;


  int sort_function( const void *a, const void *b)
{

 events p1,p2;

 p1=*(events * ) a;
 p2=*(events * ) b;


 if( p1.x-p2.x ) return p1.x-p2.x;

 return p1.c-p2.c;
}



void insert( long nod, long st, long dr, long a, long b, int val)
 {

 if( a<= st && dr <= b)
		arb[nod]=val;
 else
  {
  long mid=(st+dr)>>1;

  if (a <= mid)  insert (nod<<1, st, mid, a, b, val);

  if (b > mid )insert((nod<<1)+1, mid+1, dr, a, b, val);
  }

 }


int interrogate(long nod, long st, long dr, long a)
 {
   if( arb[nod] == 1 ) return 1;

   if( st == dr ) return 0;

  long mid=(st+dr)>>1;

  if (a <= mid) return interrogate(nod<<1, st, mid, a);

	return interrogate((nod<<1)+1, mid+1, dr, a);

 }

int main()
{

long i,max;

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

scanf("%ld%ld%ld%ld",&n,&m,&w,&h);

for(i=1;i<=n;i++)
 {
 scanf("%ld%ld",&d[i].x,&d[i].y);
 d[i].c='i';
 d[i+n].x=d[i].x+w;
 d[i+n].y=d[i].y+h;
 d[i+n].c='s';
 }
for(i+=n;i<=2*n+m;i++)
 {
 scanf("%ld%ld",&d[i].x,&d[i].y);
 d[i].c='p';
 }

  n=2*n+m;  // nr de puncte event
  m=0;   // nr de oi in ograzi


  qsort((void *)(d+1), n, sizeof(d[0]), sort_function);


 for(max=d[1].y,i=2;i<=n;i++)
 if( max < d[i].y) max=d[i].y;
 max++;


  for( i = 1 ; i <= n ; i ++ )
   {


   if( d[i].c == 'p' )
		 {	if( interrogate(1,1,max,d[i].y) ) m++; }

	 else

   if( d[i].c == 'i' )
			insert(1,1,max,d[i].y,d[i].y+h,1);

	 else

   if( d[i].c == 's' )
			insert(1,1,max,d[i].y-h,d[i].y,0);


   }



 printf("%ld\n",m);


return 0;
 }