Cod sursa(job #40518)

Utilizator stef2nStefan Istrate stef2n Data 27 martie 2007 14:40:14
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <stdio.h>
#include <stdlib.h>

#define infile "regiuni.in"
#define outfile "regiuni.out"
#define NMAX 1001
struct line{short int a,b,c;};
struct point{short int x,y;};

FILE *fin,*fout;
line L[NMAX];
point P[NMAX];
int n,m; // n puncte, m linii
short int V[NMAX];
short int aux[NMAX],ind1,ind2;
int COUNT=0;

void read_data()
  {
   int i,a,b,c,x,y;
   fin=fopen(infile,"r");
   fscanf(fin,"%d %d",&m,&n);
   for(i=1;i<=m;i++)
      {
       fscanf(fin,"%d %d %d",&a,&b,&c);
       L[i].a=a;L[i].b=b;L[i].c=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(int x, int y, line d)
  {
   if(!d.b)
     if(d.a>0)
       return ((int)d.a*x<-(int)d.c);
     else
       return ((int)d.a*x>-(int)d.c);
   else
     return ((int)d.a*x+(int)d.b*y+(int)d.c>0);
  }

int solve(short int li, short int ls, short int m)
  {
   COUNT++; if(COUNT>1001000)exit(1);
   if(li>ls)
     return 0;
   if(m==0)
     return 1;
   ind1=li;
   ind2=0;
   for(short int i=li;i<=ls;i++)
      if(sus_stanga(P[V[i]].x,P[V[i]].y,L[m]))
        V[ind1++]=V[i];
      else
        aux[ind2++]=V[i];
   for(short int i=ind1;i<=ls;i++)
      V[i]=aux[i-ind1];
   return solve(li,ind1-1,m-1)+solve(ind1,ls,m-1);
  }


int main()
{
read_data();
for(int i=0;i<n;i++)
   V[i]=i;
fout=fopen(outfile,"w");
fprintf(fout,"%d\n",solve(0,n-1,m));
fclose(fout);
return 0;
}