Cod sursa(job #40614)

Utilizator MariusMarius Stroe Marius Data 27 martie 2007 15:59:05
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <cstdio>
#include <algorithm>
using namespace std;

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

#define MAX_N 1000

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

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

short int n;

short int m;


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

void sort(entry P[], int m, int n)
{
	short int i;
	short int j;
	short int k;
	entry temp;
	bool smaller;
	for (i = 0; i < m - 1; ++ i) 
		for (j = i + 1; j < m; ++ j) {
			for (k = 0; k <= (n >> 5) + 1; ++ k)
				if (P[i].c[k] != P[j].c[k])
					break ;
			if (k <= (n >> 5) + 1)
				smaller = P[i].c[k] < P[j].c[k];
			else
				smaller = true;
			if (smaller == false)
				temp = P[i], P[i] = P[j], P[j] = temp;
		}
}

int main(void)
{
	freopen(iname, "r", stdin);
	read_in();
	short int depl;
	short int segm;
	short int i;
	short int j;
	for (i = 0; i < n; ++ i) {
		depl = i >> 5;
		segm = i & 31;
		for (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, m, n);
	short int Res = 1;
	short int thesame;
	for (i = 1; i < m; ++ i) {
		thesame = 1;
		for (j = 0; j <= (n >> 5) + 1; ++ j)
			if (P[i - 1].c[j] != P[i].c[j])
				thesame = 0;
		if (thesame == 0)
			Res ++;
	}
/	freopen(oname, "w", stdout);
	printf("%hd\n", Res);
	return 0;
}