Cod sursa(job #33260)

Utilizator stef2nStefan Istrate stef2n Data 19 martie 2007 02:09:25
Problema Ograzi Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.5 kb
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

#define infile "ograzi.in"
#define outfile "ograzi.out"
#define TYPE_LEFT 1
#define TYPE_RIGHT 2
#define TYPE_SHEEP 4
#define EVENT_MAX 200005
#define DIM_MAX 2098000
struct event{int x,y; char type;};

FILE *fin,*fout;
int N,W,H;
event E[EVENT_MAX];
int cnt=0;

bool V[DIM_MAX];
int LEFT,RIGHT,VAL;

inline void parse(char *line, int &x, int &y)
  {
   int poz=0;
   x=0;
   while(line[poz]>='0' && line[poz]<='9')
        {
         x=x*10+(line[poz]-'0');
         poz++;
        }
   poz++;
   y=0;
   while(line[poz]>='0' && line[poz]<='9')
        {
         y=y*10+(line[poz]-'0');
         poz++;
        }
  }

void citire()
  {
   int i,n,m,x,y;
   char line[20];
   fin=fopen(infile,"r");
   fscanf(fin,"%d %d %d %d\n",&n,&m,&W,&H);
   N=0;
   for(i=0;i<n;i++)
      {
       fgets(line,20,fin);
       parse(line,x,y);
       E[N].type=TYPE_LEFT;
       E[N].x=x;
       E[N++].y=y;
       E[N].type=TYPE_RIGHT;
       E[N].x=x+W;
       E[N++].y=y;
      }
   for(i=0;i<m;i++)
      {
       fgets(line,20,fin);
       parse(line,x,y);
       E[N].type=TYPE_SHEEP;
       E[N].x=x;
       E[N++].y=y;
      }
   fclose(fin);
  }

inline bool cmp(event a, event b)
  {
   if(a.x<b.x)
     return true;
   if(a.x>b.x)
     return false;
   if(a.type==b.type)
     return false;
   switch(a.type)
         {
          case TYPE_LEFT:  return true;
          case TYPE_RIGHT: return false;
          case TYPE_SHEEP: if(b.type==TYPE_LEFT)
                             return false;
                           else
                             return true;
         }
  }

inline int cmp_fct(const void *va, const void *vb)
  {
   event a=*((event*)va);
   event b=*((event*)vb);
   if(a.x<b.x)
     return -1;
   if(a.x>b.x)
     return 1;
   if(a.type==b.type)
     return 0;
   switch(a.type)
         {
          case TYPE_LEFT:  return -1;
          case TYPE_RIGHT: return 1;
          case TYPE_SHEEP: if(b.type==TYPE_LEFT)
                             return 1;
                           else
                             return -1;
         }
  }

void fill(int n, int st, int dr)
  {
   V[n]=false;
   if(st<dr)
     {
      fill(2*n,st,(st+dr)/2);
      fill(2*n+1,(st+dr)/2+1,dr);
     }
  }

void update(int n, int st, int dr)
  {
   if(LEFT<=st && dr<=RIGHT)
     {
      V[n]+=VAL;
      return;
     }
   if(LEFT<=(st+dr)/2)
     update(2*n,st,(st+dr)/2);
   if(RIGHT>(st+dr)/2)
     update(2*n+1,(st+dr)/2+1,dr);
  }

int query(int n, int st, int dr)
  {
   if(V[n])
     return 1;
   if(st==dr)
     return 0;
   if(VAL<=(st+dr)/2)
     return query(2*n,st,(st+dr)/2);
   else
     return query(2*n+1,(st+dr)/2+1,dr);
  }

void solve()
  {
   //sort(E,E+N,cmp);
   qsort(E,N,sizeof(event),cmp_fct);
   fill(1,0,1000000);
   for(int i=0;i<N;i++)
      switch(E[i].type)
            {
             case TYPE_LEFT:  LEFT=E[i].y;
                              RIGHT=E[i].y+H;
                              VAL=1;
                              update(1,0,1000000);
                              break;
             case TYPE_RIGHT: LEFT=E[i].y;
                              RIGHT=E[i].y+H;
                              VAL=-1;
                              update(1,0,1000000);
                              break;
             case TYPE_SHEEP: VAL=E[i].y;
                              cnt+=query(1,0,1000000);
                              break;
            }
  }


int main()
{
citire();
solve();
fout=fopen(outfile,"w");
fprintf(fout,"%d\n",cnt);
fclose(fout);
return 0;
}