Cod sursa(job #37481)

Utilizator razvi9Jurca Razvan razvi9 Data 25 martie 2007 10:22:36
Problema Regiuni Scor 70
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasele 11-12 Marime 0.8 kb
#include<stdio.h>
short int n,m,nr,i,j,ok,k,s;
struct{short int a,b,c;}d[1001];
struct{short int x,y;}p[1001];
short int a[1000][1001];
short int sgn(short int i,short int j)
{if(d[i].a*p[j].x+d[i].b*p[j].y+d[i].c>=0) return 1;
 else return -1;}
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",&d[i].a,&d[i].b,&d[i].c);
 for(i=1;i<=m;i++)
 {scanf("%d %d",&p[i].x,&p[i].y);
  a[0][i]=i;}
 a[0][0]=m;
 nr=0;
 for(;n;n--)
  for(i=nr;i>=0;i--)
  {ok=0;s=sgn(n,a[i][1]);
   for(j=2;j<=a[i][0];j++)
    if(sgn(n,a[i][j])!=s)
	{ok=1;
     a[nr+1][++a[nr+1][0]]=a[i][j];
     for(k=j;k<n;k++) a[i][k]=a[i][k+1];
     a[i][0]--;
     j--;}
   nr=nr+ok;}
 printf("%d",nr+1);
 fclose(stdout);
 return 0;}