Cod sursa(job #40831)

Utilizator stef2nStefan Istrate stef2n Data 27 martie 2007 19:26:45
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <stdio.h>
#include <string.h>

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

FILE *fin,*fout;
int n,m; // n puncte, m linii
point P[NMAX];
line D[NMAX];
short int marcaj[NMAX],ind;
short int aux[NMAX],indaux;
short int V[NMAX];
short int t[NMAX],indt;

void read_data()
  {
   int i;
   fin=fopen(infile,"r");
   fscanf(fin,"%d %d",&m,&n);
   for(i=0;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",&P[i].x,&P[i].y);
   fclose(fin);
  }

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

int split(short int li, short int ls, line &D)
  {
   int i,indV=li;
   indt=0;
   for(i=li;i<=ls;i++)
      if(sus_stanga(P[V[i]].x,P[V[i]].y,D))
        V[indV++]=V[i];
      else
        t[indt++]=V[i];
   for(i=indV;i<=ls;i++)
      V[i]=t[i-indV];
   if(indV==li || indV==ls-li+1)
     return -1;
   else
     return indV;
  }

int solve()
  {
   int i,j,v;

   ind=2;
   marcaj[0]=0;
   marcaj[1]=n-1;
   for(i=0;i<n;i++)
      V[i]=i;

   for(j=0;j<m;j++)
      {
       indaux=0;
       for(i=0;i<ind-1;i++)
          {
           aux[indaux++]=marcaj[i];
           v=split(marcaj[i],marcaj[i+1],D[j]);
           if(v!=-1)
             aux[indaux++]=v;
          }
       aux[indaux++]=marcaj[ind-1];
       ind=indaux;
       memcpy(marcaj,aux,indaux*sizeof(short int));
      }

   return ind-1;
  }


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