Cod sursa(job #38164)

Utilizator razvi9Jurca Razvan razvi9 Data 25 martie 2007 15:17:33
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 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)
{long s=d[i].a*p[j].x+d[i].b*p[j].y+d[i].c;
 if(s==0) return 0;
 if(s>0) return 1;
 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;j=1;
   do{s=sgn(n,a[i][j]);j++;}while(!s);
   for(j=2;j<=a[i][0];j++)
    if(sgn(n,a[i][j])&&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;}