Cod sursa(job #37620)

Utilizator Darth_NiculusIvan Nicolae Darth_Niculus Data 25 martie 2007 11:27:47
Problema Regiuni Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasa a 10-a Marime 1.79 kb
/* Ivan Nicolae - Bucuresti */
#include <stdio.h>
#include <string.h>

#define NMAX 1001
#define MMAX 1001
#define GMAX 3900
#define ZERO 0

struct dreapta
{
 short int a,b,c;
} DR[NMAX];

struct coord
{
 short int x,y;
} PT[MMAX],GRUP[GMAX][MMAX];

int i,j,n,m,LG[NMAX],dr,gr,GR_IN,GR_FI,GR_FI2,GR_IN2;

int semi_plan(int dr, int x, int y)
{
 int a=DR[dr].a, b=DR[dr].b, c=DR[dr].c;
 return (a*x+b*y+c);
}

void Sterge()
{
 int i;
 for (i=1;i<=GR_FI2;i++)
    {
     memcpy(GRUP[i],GRUP[i+1],sizeof(GRUP[i+1]));
     LG[i]=LG[i+1];
    }
 GR_FI2--;
 GR_FI--;
}

int main()
{
 freopen("regiuni.in","r",stdin);
 freopen("regiuni.out","w",stdout);

 scanf("%d%d",&n,&m);
 for (i=1;i<=n;i++)
    scanf("%d%d%d",&DR[i].a,&DR[i].b,&DR[i].c);
 for (i=1;i<=m;i++)
    scanf("%d%d",&PT[i].x,&PT[i].y);

 memset(LG,0,sizeof(LG));
 for (i=1;i<=m;i++)
    {
     GRUP[1][i].x=PT[i].x;
     GRUP[1][i].y=PT[i].y;
    }
 LG[1]=m; GR_FI=1; GR_FI2=1;

 for (dr=1;dr<=n;dr++)
    {
     GR_FI=GR_FI2;
     for (gr=1;gr<=GR_FI;gr++)
        {
         for (i=1;i<=LG[gr];i++)
            if (semi_plan(dr,GRUP[gr][i].x,GRUP[gr][i].y) < ZERO)
              {
               GRUP[GR_FI2+2][++LG[GR_FI2+2]].x = GRUP[gr][i].x;
               GRUP[GR_FI2+2][LG[GR_FI2+2]].y = GRUP[gr][i].y;
              }
              else if (semi_plan(dr,GRUP[gr][i].x,GRUP[gr][i].y) > ZERO)
                     {
                      GRUP[GR_FI2+1][++LG[GR_FI2+1]].x = GRUP[gr][i].x;
                      GRUP[GR_FI2+1][LG[GR_FI2+1]].y = GRUP[gr][i].y;
                     }
         GR_FI2+=2;
         Sterge(); gr--;
        }
     }

 int REZ=0;
 for (i=1;i<=GR_FI2;i++)
    if (LG[i])
      REZ++;

 printf("%d",REZ);

 fclose(stdin);
 fclose(stdout);
 return 0;
}