Pagini recente » Cod sursa (job #3124231) | Cod sursa (job #1993360) | Cod sursa (job #1559538) | Cod sursa (job #2764216) | Cod sursa (job #42531)
Cod sursa(job #42531)
//regiuni - infoarena
#include <stdio.h>
#define INPUT "regiuni.in"
#define OUTPUT "regiuni.out"
#define MAXNM 1001
int n, m;
int nmult;
struct list
{
list *nxt;
int x, y, mul;
}*p, *ult, *q;
struct dreapta
{
int a, b, c;
}v[MAXNM];
struct punct
{
int x, y;
};
int isleft(punct a, punct b, punct c)
{
return ((b.x-c.x) * (a.y-c.y) - (b.y-c.y) * (a.x-c.x) > 0)?-1:1;
}
int poz(int i, punct a)
{
if(v[i].b == 0) return (a.x < -v[i].c/v[i].a)?-1:1;
if(v[i].a == 0) return (a.y < -v[i].c/v[i].b)?-1:1;
punct p1, p2;
p1.x = 0; p1.y = -v[i].c/v[i].b;
p2.y = 0; p2.x = -v[i].c/v[i].a;
return isleft(a, p1, p2);
}
int main()
{
freopen(INPUT, "r", stdin);
scanf("%d %d", &n, &m);
int i;
for(i = 1; i <= n; ++i)
scanf("%d %d %d", &v[i].a, &v[i].b, &v[i].c);
p = new list;
scanf("%d %d", &p -> x, &p-> y);
p -> mul = 1;
p -> nxt = NULL;
ult = p;
for(i = 2; i <= m; ++i)
{
q = new list;
scanf("%d %d", &q -> x, &q-> y);
q -> mul = 1;
q -> nxt = NULL;
ult -> nxt = q;
ult = q;
}
int mc; nmult = 1;
int parte;
list *ult2 = NULL;
for(i = 1; i <= n; ++i)
{
list * prev; mc = 0;
int ok = 0;
for(q = p; q != ult -> nxt; q = q-> nxt)
{
punct pp; pp.x = q->x; pp.y = q->y;
if(q -> mul != mc)
{
parte = poz(i, pp);
mc = q -> mul;
}
else
{
if(parte != poz(i, pp))
{
if(!ult2) ult -> nxt = q;
else ult2 -> nxt = q;
if(!ok) q -> mul = ++nmult, ok = 1;
else q -> mul = nmult;
prev -> nxt = q -> nxt;
q -> nxt = NULL;
ult2 = q;
q = prev;
}
}
prev = q;
}
if(ult2) ult = ult2;
}
freopen(OUTPUT, "w", stdout);
printf("%d\n", nmult);
return 0;
}