Cod sursa(job #37869)

Utilizator ZuziFilip Sanziana Zuzi Data 25 martie 2007 12:56:19
Problema Regiuni Scor 10
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasa a 10-a Marime 0.95 kb
#include<stdio.h>
int n,m,v[1001],rez,num;

typedef struct
{
 int a,b,c;
}BLA;
BLA dr[1001];

int x[1001][1001];

int semn(int x,int y,int a,int b,int c)
{
return x*a+y*b+c;
}

void read()
{ int i,j;
  int xx,y;
  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",&xx,&y);
       for (j=1;j<=n;j++)
	x[i][j]=semn(xx,y,dr[j].a,dr[j].b,dr[j].c);
    }
}


int verific(int i,int j)
{
 int k;
  for (k=1;k<=n;k++)
   if ( (x[i][k]>0 && x[j][k]<0) || (x[i][k]<0 && x[j][k]>0))
    return 0;

    return 1;
}

void rezolv()
{
  int i,j;

    for (i=1;i<m;i++)
     if (!v[i])
      { num++;
	v[i]=1;
	  for (j=i+1;j<=m;j++)
	    if (verific(i,j))
	     v[j]=1;

      }

}


int main()
{
 freopen("regiuni.in","r",stdin);
 freopen("regiuni.out","w",stdout);
 read();
 rezolv();
  printf("%d",num);
 fcloseall();
 return 0;
}