Cod sursa(job #37548)

Utilizator stef2nStefan Istrate stef2n Data 25 martie 2007 10:51:26
Problema Regiuni Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasa a 10-a Marime 1.3 kb
#include <stdio.h>

#define infile "regiuni.in"
#define outfile "regiuni.out"
#define NMAX 1002
struct dreapta{int a,b,c;};
struct punct{short int x,y;};

FILE *fin,*fout;
int n,m; // n puncte, m drepte
dreapta d[NMAX];
punct p[NMAX];
punct PAUX[NMAX][NMAX];

void citire()
  {
   int i,x,y;
   fin=fopen(infile,"r");
   fscanf(fin,"%d %d",&m,&n);
   for(i=1;i<=m;i++)
      fscanf(fin,"%d %d %d",&d[i].a,&d[i].b,&d[i].c);
   for(i=0;i<n;i++)
      {
       fscanf(fin,"%d %d",&x,&y);
       p[i].x=x;
       p[i].y=y;
      }
   fclose(fin);
  }

inline bool sus_stanga(short int &x, short int &y, dreapta &d)
  {
   if(!d.b)
     if(d.a>0)
       return (d.a*(int)x<-d.c);
     else
       return (d.a*(int)x>-d.c);
   else
     return (d.a*(int)x+d.b*(int)y+d.c>0);
  }

int solve(short int n, punct *p)
  {
   short int i,count;
   if(!n)
     return 0;
   if(!m)
     return 1;

   punct *paux=PAUX[m];
   short int naux=0;
   for(i=0;i<n;i++)
      if(sus_stanga(p[i].x,p[i].y,d[m]))
        paux[naux++]=p[i];
   m--;
   count=solve(naux,paux);
   m++;

   naux=0;
   for(i=0;i<n;i++)
      if(!sus_stanga(p[i].x,p[i].y,d[m]))
        paux[naux++]=p[i];
   m--;
   count+=solve(naux,paux);
   m++;
   return count;
  }


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