Cod sursa(job #286331)

Utilizator rupraRupra C rupra Data 23 martie 2009 18:06:13
Problema Regiuni Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <algorithm>
#include <stdio.h>
#include <vector>

#define pb push_back
#define MAX 1024

using namespace std;

int n, m;
int coefA[MAX], coefB[MAX], coefC[MAX];
int cX[MAX], cY[MAX];
int grupaS[MAX];
vector <int> elemGr[MAX];

inline int sgn(long double x)
{
	if (x < 0)
		return -1;
	if (x > 0)
		return 1;
	return 0;
}

int main()
{
	freopen("regiuni.in", "r", stdin);
	freopen("regiuni.out", "w", stdout);

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++)
		scanf("%d %d %d", &coefA[i], &coefB[i], &coefC[i]);

	for (int i = 1; i <= m; elemGr[1].pb(i), i++)
		scanf("%d %d", &cX[i], &cY[i]);

	int nrGrupe = 1;
	for (int dr = 1; dr <= n; dr++)
	{
		for (int i = 1; i <= m; i++)
		{
			double s1 = (cX[i] * coefA[dr]) + (cY[i] * coefB[dr]) + coefC[dr];

			if (sgn(s1) == 1)
				grupaS[i] = 1;
			else grupaS[i] = 2;
		}

		for (int gr = 1; gr <= nrGrupe; gr++)
		{
			int s1 = grupaS[elemGr[gr][0]];

			for (int i = 1, gn = 0; i < elemGr[gr].size(); i++)
				if (grupaS[elemGr[gr][i]] != s1)
				{
					if (gn)
						elemGr[nrGrupe].pb(elemGr[gr][i]);
					else elemGr[++nrGrupe].pb(elemGr[gr][i]);

					swap(elemGr[gr][i], elemGr[gr][elemGr[gr].size() - 1]);
					elemGr[gr].pop_back();

					gn = 1;
					i--;
				}
		}
	}

	printf("%d\n", nrGrupe);

	fclose(stdin);
	fclose(stdout);
	return 0;
}