Pagini recente » Cod sursa (job #2204178) | Cod sursa (job #3275351) | Cod sursa (job #1600451) | Cod sursa (job #3138101) | Cod sursa (job #86411)
Cod sursa(job #86411)
#include <stdio.h>
#define infile "regiuni.in"
#define outfile "regiuni.out"
#define nmax 1001
struct dreapta
{
int a,b,c;
};
struct punct
{
int x, y;
};
struct nod
{
int inf;
struct nod * urm;
};
typedef nod * list;
int n, m, i, j, k, rez, gmax=1;
dreapta dr[nmax];
punct pct[nmax];
list v[nmax];
void readdata();
void writedata();
void solve();
int poz(punct,dreapta);
void init();
int main()
{
readdata();
solve();
writedata();
return 0;
}
void readdata()
{
freopen(infile, "r", stdin);
scanf("%d %d\n", &n, &m);
for (i=1; i<=n; i++)
scanf("%d %d %d\n", &dr[i].a, &dr[i].b, &dr[i].c);
for (i=1; i<=m; i++)
scanf("%d %d\n", &pct[i].x, &pct[i].y);
fclose(stdin);
}
void writedata()
{
freopen(outfile, "w", stdout);
printf("%d\n", gmax);
fclose(stdout);
}
void solve()
{
init();
int temp, loc, add;
list p, last;
for (i=1; i<=n; i++)
{
temp=0;
for (j=1; j<=gmax; j++)
{
add=0;
loc=poz(pct[v[j]->inf],dr[i]);
for (p=v[j]->urm, last=v[j]; p; p=p->urm)
if (poz(pct[p->inf],dr[i])!=loc)
{
last->urm=last->urm->urm;
if (add)
{
p->urm=v[gmax+temp];
v[gmax+temp]=p;
p=last;
}
else
{
temp++;
add=1;
p->urm=v[gmax+temp];
v[gmax+temp]=p;
p=last;
}
}
else last=last->urm;
}
gmax+=temp;
}
}
int poz(punct p, dreapta d)
{
return d.a*p.x+d.b*p.y+d.c<0;
}
void init()
{
v[1]=new nod;
v[1]->inf=1;
v[1]->urm=NULL;
list last=v[1];
for (i=2; i<=m; i++)
{
list p=new nod;
p->inf=i;
p->urm=NULL;
last->urm=p;
last=p;
}
}