Cod sursa(job #37487)

Utilizator MariusMarius Stroe Marius Data 25 martie 2007 10:26:18
Problema Regiuni Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasele 11-12 Marime 1.17 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const char iname[] = "regiuni.in";
const char oname[] = "regiuni.out";

#define MAX_N 1007

struct entry {
	unsigned int c[MAX_N / 32 + 5];
	int x;
	int y;
} P[MAX_N];

int a[MAX_N], b[MAX_N], c[MAX_N];

int n;

int m;


void read_in(void)
{
	scanf("%d %d", & n, & m);
	for (int i = 0; i < n; ++ i)
		scanf("%d %d %d", a + i, b + i, c + i);
	for (int i = 0; i < m; ++ i)
		scanf("%d %d", & P[i].x, & P[i].y);
}

int cmp(entry z, entry w)
{
	for (int i = 0; i <= (n >> 5) + 2; ++ i)
		if (z.c[i] != w.c[i])   return z.c[i] < w.c[i];
	return 1;
}

int main(void)
{
	freopen(iname, "r", stdin);
	read_in();
	for (int i = 0; i < n; ++ i) {
		int depl = i >> 5;
		int segm = i & 31;
		for (int j = 0; j < m; ++ j)
			if (a[i] * P[j].x + b[i] * P[j].y + c[i] < 0)
				P[j].c[depl] |= 1 << segm;
	}
	sort(P, P + m, cmp);
	int Res = 1;
	for (int i = 1; i < m; ++ i) {
		int thesame = 1;
		for (int j = 0; j <= (n >> 5) + 2; ++ j)
			if (P[i - 1].c[j] != P[i].c[j])
				thesame = 0;
		if (thesame == 0)
			Res ++;
	}
	freopen(oname, "w", stdout);
	printf("%d\n", Res);
	return 0;
}