Pagini recente » Cod sursa (job #2705688) | Cod sursa (job #3191599) | Cod sursa (job #2084241) | Cod sursa (job #744286) | Cod sursa (job #43815)
Cod sursa(job #43815)
#include<stdio.h>
#define sc scanf
#define pr printf
#define Nmax 1024
#define Mmax 1024
struct lista
{
int inf;
lista *urm;
};
struct punct
{
int x,y;
};
struct dreapta
{
int a,b,c;
};
int N,M,v[Mmax];
int NrG;
punct P[Mmax];
dreapta D[Nmax];
lista *Gr[Mmax];
void cit()
{
int i;
freopen("regiuni.in","r",stdin);
sc("%d%d",&N,&M);
for(i=1;i<=N;i++)
sc("%d%d%d",&D[i].a,&D[i].b,&D[i].c);
for(i=1;i<=M;i++)
sc("%d%d",&P[i].x,&P[i].y);
}
int semn(dreapta d,punct p)
{
if(d.a*p.x+d.b*p.y+d.c<0)
return -1;
return 1;
}
void rez()
{
int i,j,x,NrGNou,GrNou;
lista *c,*d,*e;
for(i=1;i<=M;i++)
if( semn(D[1],P[i])<0 )
v[i]=-1;
else
v[i]=1;
NrG=1;
Gr[1]=new lista;
Gr[1]->urm=NULL;
for(i=1,c=Gr[1];i<=M;i++)
{
c->urm=new lista;
c=c->urm;
c->inf=i;
c->urm=NULL;
}
x=v[1];
GrNou=0;
for(c=Gr[1]->urm;c;c=c->urm)
if(v[c->inf]!=x)
{
if(Gr[NrG+1]==NULL)
{
GrNou=1;
Gr[NrG+1]=new lista;
Gr[NrG+1]->urm=NULL;
d=Gr[NrG+1];
}
d=d->urm;
d=new lista;
d->inf=c->inf;
d->urm=NULL;
}
if(GrNou)
NrG++;
for(i=2;i<=N;i++)
{
for(j=1;j<=M;j++)
if( semn(D[i],P[j])<0 )
v[j]=-1;
else
v[j]=1;
NrGNou=NrG;
for(j=1;j<=NrG;j++)
{
GrNou=0;
e=Gr[j]->urm;
if(e)
{
x=v[Gr[j]->urm->inf];
for(c=Gr[j]->urm->urm;c;c=c->urm)
{
if(c&&v[c->inf]!=x)
{
if(Gr[NrGNou+1]==NULL)
{
GrNou=1;
Gr[NrGNou+1]=new lista;
Gr[NrGNou+1]->urm=NULL;
d=Gr[NrGNou+1];
}
d->urm=new lista;
d=d->urm;
d->inf=c->inf;
d->urm=NULL;
e->urm=c->urm;
delete c;
}
else
e=c;
}
}
if(GrNou)
NrGNou++;
}
NrG=NrGNou;
}
}
void scr()
{
freopen("regiuni.out","w",stdout);
printf("%d\n",NrG);
fclose(stdout);
}
int main()
{
cit();
rez();
scr();
return 0;
}