Pagini recente » Cod sursa (job #1380868) | Cod sursa (job #579932) | Cod sursa (job #71235) | Cod sursa (job #1245585) | Cod sursa (job #40846)
Cod sursa(job #40846)
#include <stdio.h>
#define infile "regiuni.in"
#define outfile "regiuni.out"
#define NMAX 1002
struct point {short int x,y;};
struct line {short int a,b,c;};
FILE *fin,*fout;
int n,m; // n puncte, m linii
point P[NMAX];
line D[NMAX];
short int marcaj[NMAX],ind;
short int aux[NMAX],indaux;
short int V[NMAX];
short int t[NMAX],indt;
void read_data()
{
int i;
fin=fopen(infile,"r");
fscanf(fin,"%d %d",&m,&n);
for(i=0;i<m;i++)
fscanf(fin,"%d %d %d",&D[i].a,&D[i].b,&D[i].c);
for(i=0;i<n;i++)
fscanf(fin,"%d %d",&P[i].x,&P[i].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 split(short int li, short int ls, line &D)
{
short int i,indV=li;
indt=0;
for(i=li;i<=ls;i++)
if(sus_stanga(P[V[i]].x,P[V[i]].y,D))
V[indV++]=V[i];
else
t[indt++]=V[i];
for(i=indV;i<=ls;i++)
V[i]=t[i-indV];
if(indV==li || indV==ls+1)
return -1;
else
return indV;
}
short int solve()
{
int i,j,v;
ind=2;
marcaj[0]=-1;
marcaj[1]=n-1;
for(i=0;i<n;i++)
V[i]=i;
for(j=0;j<m;j++)
{
indaux=0;
for(i=0;i<ind-1;i++)
{
aux[indaux++]=marcaj[i];
v=split(marcaj[i]+1,marcaj[i+1],D[j]);
if(v!=-1)
aux[indaux++]=v-1;
}
aux[indaux++]=marcaj[ind-1];
ind=indaux;
for(i=0;i<indaux;i++)
marcaj[i]=aux[i];
}
return ind-1;
}
int main()
{
read_data();
fout=fopen(outfile,"w");
fprintf(fout,"%d\n",solve());
fclose(fout);
return 0;
}