Pagini recente » Cod sursa (job #1750276) | Cod sursa (job #2752656) | Cod sursa (job #1993071) | Cod sursa (job #1120720) | Cod sursa (job #43844)
Cod sursa(job #43844)
#include<stdio.h>
#define sc scanf
#define pr printf
#define Nmax 1024
#define Mmax 1024
struct punct
{
int x,y;
};
struct dreapta
{
int a,b,c;
};
int N,M,v[Mmax];
int NrG;
punct P[Mmax];
dreapta D[Nmax];
int Gr[Mmax][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,k,y,NrGNou,GrNou;
for(i=1;i<=M;i++)
if( semn(D[1],P[i])<0 )
v[i]=-1;
else
v[i]=1;
NrG=1;
for(i=1;i<=M;i++)
Gr[1][i]=i;
Gr[1][0]=M;
x=v[1];
GrNou=0;
y=0;
for(i=2;i<=M;i++)
if(v[i]!=x)
{
GrNou=1;
Gr[NrG+1][0]++;
Gr[NrG+1][Gr[NrG][0]]=i;
}
else
{
y++;
Gr[NrG][y]=i;
}
Gr[NrG][0]=y;
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;
x=v[Gr[j][1]];
y=0;
for(k=2;k<=Gr[j][0];k++)
if(v[Gr[j][k]]!=x)
{
GrNou=1;
Gr[NrGNou+1][0]++;
Gr[NrGNou+1][Gr[NrGNou][0]]=Gr[j][k];
}
else
{
y++;
Gr[j][y]=Gr[j][k];
}
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;
}