Cod sursa(job #42591)

Utilizator marinaMarina Horlescu marina Data 29 martie 2007 12:48:24
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
//regiuni - infoarena
#include <stdio.h>
#include <string.h>
#define INPUT "regiuni.in"
#define OUTPUT "regiuni.out"
#define MAXNM 1001

int n, m;
int parte[MAXNM], mul[MAXNM], ok[MAXNM];
struct dreapta
{
	float a, b, c;
}v[MAXNM];

struct punct
{
	float x, y;
}p[MAXNM];

inline int poz(int i, punct a)
{
	if(v[i].b == 0) return (a.x <(float) -v[i].c/v[i].a)?-1:1;
	if(v[i].a == 0) return (a.y <(float) -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 ((p1.x-p2.x) * (a.y-p2.y)  - (p1.y-p2.y) * (a.x-p2.x) > 0)?-1:1;
}
int main()
{
	freopen(INPUT, "r", stdin);
	scanf("%d %d", &n, &m);
	int i;
	for(i = 1; i <= n; ++i)
		scanf("%f %f %f", &v[i].a, &v[i].b, &v[i].c);
	
	for(i = 1; i <= m; ++i)
		scanf("%f %f", &p[i].x, &p[i].y),
		mul[i] = 1;
	
	int j, nmult = 1;
	for(i = 1; i <= n; ++i)
	{
		memset(parte, 0, sizeof(parte));
		memset(ok, 0, sizeof(ok));
		for(j = 1; j <= m; ++j)
		{
			if(!parte[mul[j]]) parte[mul[j]] = poz(i, p[j]);
			else if(parte[mul[j]] != poz(i, p[j]))
			{
				if(!ok[mul[j]]) 
				{
					ok[mul[j]] = ++nmult;
					mul[j] = nmult;
				}
				else mul[j] = ok[mul[j]];
			}
			
		}
	
	}
	freopen(OUTPUT, "w", stdout);
	printf("%d\n", nmult);
	return 0;
}