Pagini recente » Cod sursa (job #774967) | Cod sursa (job #104930) | Cod sursa (job #2135056) | Cod sursa (job #2631837) | Cod sursa (job #40549)
Cod sursa(job #40549)
#include <stdio.h>
#define infile "regiuni.in"
#define outfile "regiuni.out"
#define NMAX 1001
struct line{short int a,b,c;};
struct point{short int x,y;};
FILE *fin,*fout;
line L[NMAX];
point P[NMAX];
int n,m; // n puncte, m linii
short int V[NMAX];
short int aux[NMAX],ind2;
void read_data()
{
int i,a,b,c,x,y;
fin=fopen(infile,"r");
fscanf(fin,"%d %d",&m,&n);
for(i=1;i<=m;i++)
{
fscanf(fin,"%d %d %d",&a,&b,&c);
L[i].a=a;L[i].b=b;L[i].c=c;
}
for(i=0;i<n;i++)
{
fscanf(fin,"%d %d",&x,&y);
P[i].x=x;P[i].y=y;
}
fclose(fin);
}
inline bool sus_stanga(short int &x, short int &y, line &d)
{
if(!d.b)
if(d.a>0)
return ((int)d.a*(int)x<-(int)d.c);
else
return ((int)d.a*(int)x>-(int)d.c);
else
return ((int)d.a*(int)x+(int)d.b*(int)y+(int)d.c>0);
}
short int solve(short int li, short int ls)
{
if(li>ls)
return 0;
if(m==0)
return 1;
short int i,ind1=li;
ind2=0;
for(i=li;i<=ls;i++)
if(sus_stanga(P[V[i]].x,P[V[i]].y,L[m]))
V[ind1++]=V[i];
else
aux[ind2++]=V[i];
for(i=ind1;i<=ls;i++)
V[i]=aux[i-ind1];
m--;
i=solve(li,ind1-1)+solve(ind1,ls);
m++;
return i;
}
int main()
{
read_data();
for(int i=0;i<n;i++)
V[i]=i;
fout=fopen(outfile,"w");
fprintf(fout,"%d\n",solve(0,n-1));
fclose(fout);
return 0;
}