Cod sursa(job #362243)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 8 noiembrie 2009 17:48:54
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <stdio.h>
#define Nmax 1001

struct dreapta{
	int a,b,c;
} dr[Nmax];
struct punct{
	int x,y;
} p[Nmax];

int gr[Nmax],side[Nmax],cul[Nmax];
int n,m,i,nrg,semn,j;

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",&p[i].x,&p[i].y), gr[i]=1;
   nrg=1;

   for(i=1;i<=n;++i){
     	for(j=1;j<=nrg;++j) side[j]=0,cul[j]=0;

   	for(j=1;j<=m;++j){
      	semn= dr[i].a*p[j].x + dr[i].b*p[j].y + dr[i].c > 0 ? 1 : -1 ;
         if(side[gr[j]] == 0 ) side[gr[j]]=semn;else
         if(semn != side[gr[j]])
           if(cul[gr[j]] == 0) cul[gr[j]]=++nrg,gr[j]=nrg;
           else gr[j]=cul[gr[j]];
      }
   }

   printf("%d\n",nrg);
   fclose(stdin); fclose(stdout);
   return 0;
}