Cod sursa(job #42531)

Utilizator marinaMarina Horlescu marina Data 29 martie 2007 11:55:32
Problema Regiuni Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
//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;
}