Cod sursa(job #28975)

Utilizator y2kClaudiu Guiman y2k Data 8 martie 2007 14:58:14
Problema Ograzi Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.91 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define IN_FILE "ograzi.in"
#define OUT_FILE "ograzi.out"
struct lista {
 float pctX,pctY;
 int drpX,drpY;
 lista *urm;
};
FILE *f1,*f2;
int r,n,m,w,h,x,y,nr;
float knuth;
char s[100];
lista *a[50001];
//inline int hmrand(int x)
//{
//}
inline int hash(float x)
{

return((int)(((knuth*x)-floor(knuth*x))*n));
// return (r*(int)(x))%n;
}
inline int exista(int pctx,int pcty, int x, int y)
{
 if(pctx>=x && pctx<=(x+w) && pcty>=y && pcty<=(y+h))
  return 1;
 return 0;
}
void parsare1()
{
 int i;
 s[strlen(s)-1]='\0';
 i=0;
 n=0;
 m=0;
 w=0;
 h=0;
 while(s[i]!=' ')
 {
  n=n*10+s[i]-'0';
  ++i;
 }
 ++i;
 while(s[i]!=' ')
 {
  m=m*10+s[i]-'0';
  ++i;
 }
 ++i;
 while(s[i]!=' ')
 {
  w=w*10+s[i]-'0';
  ++i;
 }
 ++i;
 while(s[i]!='\0')
 {
  h=h*10+s[i]-'0';
  ++i;
 }
}
void parsare2()
{
 int i;
 s[strlen(s)-1]='\0';
 i=0;
 x=0;
 y=0;
 while(s[i]!=' ')
 {
  x=x*10+s[i]-'0';
  ++i;
 }
 ++i;
 while(s[i]!='\0')
 {
  y=y*10+s[i]-'0';
  ++i;
 }
}
lista *cautare_lista(lista *&p,float x1,float y1)
{
 lista *q;
 q=p;
 while(q)
 {
  if(q->pctX==x1 && q->pctY==y1)
   return q;
  q=q->urm;
 }
 return NULL;
}
void inserare_lista(lista *&p,float x1,float y1, int x2,int y2)
{
 if(p==NULL)
 {
  p=new lista;
  p->pctX=x1;
  p->pctY=y1;
  p->drpX=x2;
  p->drpY=y2;
  p->urm=NULL;
 }
 else
 {
  lista *q,*t;
  q=p;
  t=new lista;
  t->pctX=x1;
  t->pctY=y1;
  t->drpX=x2;
  t->drpY=y2;
  t->urm=NULL;
  while(q->urm)
  q=q->urm;
  q->urm=t;
 }
}
void inserare(float x1,float y1, int x2, int y2)
{
 inserare_lista(a[hash(x1)],x1,y1,x2,y2);
}
lista *cauta(float x1, float y1)
{
 return cautare_lista(a[hash(x1)],x1,y1);
}
int main()
{
 int i,u;
 f1=fopen(IN_FILE,"r");
 f2=fopen(OUT_FILE,"w");
 fgets(s,100,f1);
 parsare1();
 u=n;
 if(n>=25000)
  n=49999;
  else
  {
  if(n>=10000)
   n=24989;
   else
   {
   if(n>=5000)
     n=10007;
     else
     {
     if(n%2==0)
     n++;
     }
   }
  }
 knuth=(sqrt(5)-1)/2; 
 for(i=0; i<u; ++i)
 {
  fgets(s,100,f1);
  parsare2();
     inserare((((x-1)/w)+1)*w+0.5,(((y-1)/h)+1)*h+0.5,x,y);
 }
 nr=0;
 lista *q1,*q2,*q3,*q4;
 for(i=0; i<m; ++i)
 {
  fgets(s,100,f1);
  parsare2();
  q1=cauta(((((x-1)/w)+1))*w+0.5,((((y-1)/h)+1))*h+0.5);
  if(q1!=NULL && exista(x,y,q1->drpX,q1->drpY))
   {
   ++nr;
   }
   else
   {
  q2=cauta(((((x-1)/w)+1))*w+0.5-w,((((y-1)/h)+1))*h+0.5);
    if(q2!=NULL && exista(x,y,q2->drpX,q2->drpY))
     ++nr;
     else
     {
  q3=cauta(((((x-1)/w)+1))*w+0.5,((((y-1)/h)+1))*h+0.5-h);
  if(q3!=NULL && exista(x,y,q3->drpX,q3->drpY))
   ++nr;
   else
   {
  q4=cauta(((((x-1)/w)+1))*w+0.5-w,((((y-1)/h)+1))*h+0.5-h);
    if(q4!=NULL && exista(x,y,q4->drpX,q4->drpY))
   ++nr;
  }
  }
  }
 }
 fprintf(f2,"%d",nr);
 fclose(f1);
 fclose(f2);
 return 0;
}